Qinshihuang's Blog

tmc的小窝

0%

李超线段树

发表于 更新于

模板 P4097

有 $n$ 次操作，每次操作如下：

  1. 在平面内插入一条线段。
  2. 查询某点最高的线段高度。

时间复杂度 $O(n\log^2 n)$，强制在线。

李超线段树模板题，核心思想是标记永久化。

首先在线段树的每个节点记录当前节点的“优势线段”，即在区间中点高度最高的线段编号。

初始时优势线段标号为 $0$。

在修改时，对于当前修改到的区间和目标的区间，若他们相等，则插入线段；否则就拆分区间递归向下搜索，这些部分和正常线段树一样。

考虑插入线段到区间怎么写。

首先若当前即将插入的线段的中点高度高于优势线段的高度，那么当前线段可以取代优势线段，此时应该交换这两条线段。至于为什么后面有用处。

其次判断有没有递归向下修改的意义。可以发现若当前的优势线段左右高度均高于修改的线段，那么就没有修改的意义了。

这里，当前优势线段和修改的线段都是已经交换完后的线段，这也是交换的意义，可以减少很多代码编写的难度。

可以发现两条线段只有一个交点，所以最多只有一半区间需要被继续修改，可以发现是有交点的一半需要继续修改，此时根据两端高度来判断哪边有交点即可。

其实判断哪边有交点是需要根据斜率来综合分类讨论的，但是注意优势线段的中点要比当前线段的中点要高，这样只需要找到哪边优势线段要比当前线段低就可以判定哪边有交点了。这也体现出前边交换两条线段的目的。

最后查询时要注意当目前插入的线段成为优势线段时，它不会继续向下递归，而是换成被替换的“前优势线段”进行递归，也就是当前线段被固定了。所以在查询时需要在沿路的所有线段中找最高点。

时间复杂度：每条线段都会在线段树上被分解成 $O(\log n)$ 个区间，每个区间最多会往下修改 $O(\log n)$ 次，所以总时间复杂度时 $O(n\log^2 n)$。

特别的，如果插入直线，只需要 $O(n\log n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
#define ll long long
#define il inline
#define db double
#define N 100005
#define lc(x) (x<<1)
#define rc(x) (x<<1)|1
il ll read() {
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') {f=-1;} c=getchar();}
	while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
const db eps=1e-8;
const int n=39989;
const db inf=1e18;
struct Line {
	db k,b;
	int id;
	Line() {}
	Line(db x1,db y1,db x2,db y2,int i) {
		id=i;
		if(fabs(x1-x2)<eps) {
			k=0.0,b=max(y1,y2);
			return;
		}
		k=(y1-y2)/(x1-x2);
		b=y1-k*x1;
	}
};
struct sgt {
	int maxn;
};
sgt tr[N<<2];
int q,lans=0;
Line a[N];
il db f(int i,db x) {
	return a[i].k*x+a[i].b;
}
il void modify(int nl,int nr,int l,int r,int now,int id) {
	if(l==nl&&r==nr) {
		if(tr[now].maxn==0) {
			tr[now].maxn=id;
			return;
		}
		int mid=(l+r)>>1;
		if(fabs(f(tr[now].maxn,mid)-f(id,mid))<eps) {
			if(tr[now].maxn>id) swap(id,tr[now].maxn);
		}
		else if(f(tr[now].maxn,mid)-f(id,mid)<=-eps) swap(tr[now].maxn,id);
		bool fl=(f(tr[now].maxn,l)-f(id,l)>=eps);
		bool fr=(f(tr[now].maxn,r)-f(id,r)>=eps);
		if(fl&&fr) return;
		if(!fl) modify(nl,mid,l,mid,lc(now),id);
		if(!fr) modify(mid+1,nr,mid+1,r,rc(now),id);
		return;
	}
	int mid=(l+r)>>1;
	if(nr<=mid) modify(nl,nr,l,mid,lc(now),id);
	else if(mid<nl) modify(nl,nr,mid+1,r,rc(now),id);
	else modify(nl,mid,l,mid,lc(now),id),modify(mid+1,nr,mid+1,r,rc(now),id);
}
il int query(int p,int l,int r,int now) {
	if(l==r) return tr[now].maxn;
	int mid=(l+r)>>1,ans=0;
	if(p<=mid) ans=query(p,l,mid,lc(now));
	else ans=query(p,mid+1,r,rc(now));
	if(fabs(f(tr[now].maxn,p)-f(ans,p))<eps) return min(tr[now].maxn,ans);
	else {
		if(f(tr[now].maxn,p)-f(ans,p)>=eps) return tr[now].maxn;
		else return ans;
	}
}
int tot=0;
int main() {
	a[0].k=a[0].b=-inf;
	q=read();
	for(int i=1;i<=q;i++) {
		int opt=read();
		if(opt==0) {
			int k=(read()+lans-1)%n+1;
			lans=query(k,1,n,1);
			printf("%d\n",lans);
		}
		else {
			int x0=(read()+lans-1)%n+1,y0=(read()+lans-1)%(1000000000)+1,x1=(read()+lans-1)%n+1,y1=(read()+lans-1)%(1000000000)+1;
			if(x0>x1) {
				swap(x0,x1);
				swap(y0,y1);
			}
			a[++tot]=Line(x0,y0,x1,y1,tot);
			modify(x0,x1,1,n,1,tot);
		}
	}
	return 0;
}

练习题

P4069

给定一棵 $n$ 个点的无根树，每条边有长度，每个点有一个数 $c_u$，初始为 $123456789123456789$。

接下来有 $m$ 个操作，两个类型：

  1. 对 $s$ 到 $t$ 的路径实施操作，对于所有在路径上的点 $u$，记 $dis_u$ 为 $s$ 到 $u$ 的距离，将 $a_u\leftarrow\min\{c_u,a\cdot dis_u+b\}$。
  2. 查询 $s$ 到 $t$ 路径上最小数。

看到 $a\cdot dis_u+b$ 这个形式可以想到李超树维护。

但是李超树插入的线段中自变量 $x$ 是单一的，但是这里 $dis_u$ 是会随着 $u$ 的变化而变化，不能直接把 $dis_u$ 作为自变量。

考虑变形式子，将 $s-t$ 分成 $s-\mathrm{lca}$ 和 $\mathrm{lca}-t$，记 $dep_u$ 是 $1$ 做根时 $u$ 的深度。

对于第一部分：

对于第二部分：

这样就把会变的 $dis_u$ 变成了恒定的 $dep_u$，把这个东西作为自变量丢到李超树上就可以了。

这里有一个注意点：在李超树板子里求线段的高度时只需要计算 $kx+b$，但是这里的自变量是 $dep$，而且还是以线段树树剖后的 dfn 序为下标的，所以查询时要写

这样就可以了，记得开 long long。

注意树剖别写错。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long
#define il inline
#define N 100005
#define lc(x) (x<<1)
#define rc(x) (x<<1)|1
il ll read() {
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') {f=-1;} c=getchar();}
	while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
const ll INF=1e18;
struct Edge {
	ll next,u,v,w;
};
struct sgt {
	ll l,r,maxid,minn;
};
sgt tr[N<<2];
ll n,m;
Edge edge[N<<1];
ll head[N],num_edge;
il void add_edge(ll u,ll v,ll w) {
	edge[++num_edge].next=head[u];
	edge[num_edge].u=u,edge[num_edge].v=v,edge[num_edge].w=w;
	head[u]=num_edge;
}
ll fa[N],dep[N],son[N],siz[N];
ll seg[N],rev[N],top[N],tot;
il void dfs1(ll u,ll f,ll ww) {
	fa[u]=f,dep[u]=dep[f]+ww,siz[u]=1;
	for(int i=head[u];i;i=edge[i].next) {
		ll v=edge[i].v,w=edge[i].w;
		if(v==f) continue;
		dfs1(v,u,w);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]]) son[u]=v;
	}
}
il void dfs2(ll u,ll f) {
	if(son[u]!=0) {
		seg[son[u]]=++tot;
		rev[tot]=son[u];
		top[son[u]]=top[u];
		dfs2(son[u],u);
	} 
	for(int i=head[u];i;i=edge[i].next) {
		int v=edge[i].v;
		if(seg[v]) continue;
		seg[v]=++tot;
		rev[tot]=v;
		top[v]=v;
		dfs2(v,u);
	}
}
struct Line {
	ll k,b,id;
	Line() {}
	Line(ll a,ll bb,ll i) {
		k=a,b=bb,id=i;
	}
	ll val(ll x) {
		return k*dep[rev[x]]+b;
	}
};
Line a[N<<1];
il void push_up(ll now) {
	tr[now].minn=min(tr[lc(now)].minn,tr[rc(now)].minn);
	tr[now].minn=min(tr[now].minn,min(a[tr[now].maxid].val(tr[now].l),a[tr[now].maxid].val(tr[now].r)));
}
il void build(ll now,ll l,ll r) {
	tr[now].l=l,tr[now].r=r;
	if(l==r) {
		tr[now].maxid=0,tr[now].minn=123456789123456789ll;
		return;
	}
	ll mid=(l+r)>>1;
	build(lc(now),l,mid);
	build(rc(now),mid+1,r);
	push_up(now);
}
il void cover(ll l,ll r,ll now,ll id) {
    ll mid=(l+r)>>1;
    if(a[id].val(mid)<a[tr[now].maxid].val(mid)) swap(id,tr[now].maxid);
    if(l==r) {
    	tr[now].minn=min(tr[now].minn,min(a[tr[now].maxid].val(l),a[tr[now].maxid].val(r)));
    	return;
	}
    if(a[id].val(l)<a[tr[now].maxid].val(l)) cover(l,mid,lc(now),id);
    if(a[id].val(r)<a[tr[now].maxid].val(r)) cover(mid+1,r,rc(now),id);
    push_up(now);
    return;
}
il void modify(ll nl,ll nr,ll l,ll r,ll now,ll id) {
    if(r<nl||nr<l) return;
    if(nl<=l&&r<=nr) {
        cover(l,r,now,id);
        return;
    }
    ll mid=(l+r)>>1;
    modify(nl,nr,l,mid,lc(now),id);
	modify(nl,nr,mid+1,r,rc(now),id);
	push_up(now);
    return;	
}
il ll query(ll qx,ll qy,ll l,ll r,ll now) {
	if(qx<=l&&r<=qy) return tr[now].minn;
	if(qy<l||r<qx) return INF;
	ll ans=min(a[tr[now].maxid].val(max(qx,l)),a[tr[now].maxid].val(min(qy,r))),mid=(l+r)>>1;
	return min(ans,min(query(qx,qy,l,mid,lc(now)),query(qx,qy,mid+1,r,rc(now))));
}
il ll LCA(ll x,ll y) {
	while(top[x]!=top[y]) {
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	return x;
}
il void add(ll x,ll y,ll id) {
	ll fx=top[x],fy=top[y];
	while(fx!=fy) {
		if(dep[fx]<dep[fy]) swap(x,y),swap(fx,fy);
		modify(seg[fx],seg[x],1,n,1,id);
		x=fa[fx];
		fx=top[x];
	}
	if(dep[x]>dep[y]) swap(x,y);
	modify(seg[x],seg[y],1,n,1,id);
}
il ll ask(ll x,ll y) {
	ll ans=INF,fx=top[x],fy=top[y];
	while(fx!=fy) {
		if(dep[fx]<dep[fy]) swap(x,y),swap(fx,fy);
		ans=min(ans,query(seg[fx],seg[x],1,n,1));
		x=fa[fx],fx=top[x];
	}
	if(dep[x]>dep[y]) swap(x,y);
	ans=min(ans,query(seg[x],seg[y],1,n,1));
	return ans;
}
int main() {
	a[0].b=123456789123456789ll,a[0].k=0;
	n=read(),m=read();
	for(int i=1;i<n;i++) {
		ll u=read(),v=read(),w=read();
		add_edge(u,v,w);
		add_edge(v,u,w);
	}
	tot=1;
	seg[1]=1;
	rev[1]=1;
	top[1]=1;
	dfs1(1,0,0);
	dfs2(1,0);
	build(1,1,n);
	tot=0;
	for(int i=1;i<=m;i++) {
		ll opt=read(),s=read(),t=read();
		if(opt==1) {
			ll AAA=read(),BBB=read();
			ll lca=LCA(s,t);
			a[++tot]=Line(-AAA,AAA*dep[s]+BBB,tot);
			add(s,lca,tot);
			a[++tot]=Line(AAA,dep[s]*AAA-2*dep[lca]*AAA+BBB,tot);
			add(lca,t,tot);
		}
		else {
			printf("%lld\n",ask(s,t));
		}
		//for(int i=1;i<=n;i++) printf("%lld ",query(seg[i],seg[i],1,n,1));
		//putchar('\n');
	}
	return 0;
}