线段树寄巧
线段树优化建图
对于一类从点 到区间 连边,或者像是 向点 连边的建图时,我们可以把区间变成若干个线段树上的节点,然后将链接节点与线段树上节点即可,对于上述的两种建边,需要使用两颗线段树,一颗父亲节点指向孩子节点,边权为 ,叫做入树;另一个孩子节点指向父亲节点,边权为 ,叫做出树.
例题- CF786B Legacy
code
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
#include <bits/stdc++.h>
#define _F(x,y,z) for(int x=y;x<=z;x++)
#define F_(x,z,y) for(int x=z;x>=y;x--)
#define TF(x,y,z) for(int x=head[y],z;x;x=nex[x])
#define lson (now<<1)
#define rson (now<<1|1)
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;
typedef double dou;
typedef const int ci;
typedef pair<ll,ll> pll;
ci maxn=2e6+10;
ll n,head[maxn],to[maxn],nex[maxn],val[maxn],tot;
ll ti[maxn],tu[maxn],cnt,q,s,f[maxn];
bool vis[maxn];
void add(int x,int y,ll v=0ll)
{
to[++tot]=y;
nex[tot]=head[x];
head[x]=tot;
val[tot]=v;
}
void build(int now,int l,int r)
{
if(l==r)
{
ti[now]=tu[now]=l;
return ;
}
build(lson,l,mid);
build(rson,mid+1,r);
ti[now]=++cnt,tu[now]=++cnt;
add(ti[now],ti[lson]);
add(ti[now],ti[rson]);
add(tu[lson],tu[now]);
add(tu[rson],tu[now]);
}
void fixin(int now,int l,int r,int x,int y,int f,ll c)
{
if(x<=l&&r<=y)
{
add(f,ti[now],c);
return;
}
if(x<=mid)
fixin(lson,l,mid,x,y,f,c);
if(y>mid)
fixin(rson,mid+1,r,x,y,f,c);
}
void fixout(int now,int l,int r,int x,int y,int f,ll c)
{
if(x<=l&&r<=y)
{
add(tu[now],f,c);
return ;
}
if(x<=mid)
fixout(lson,l,mid,x,y,f,c);
if(y>mid)
fixout(rson,mid+1,r,x,y,f,c);
}
priority_queue<pll,vector<pll>,greater<pll> >pq;
void dij(int s)
{
memset(f,0x3f,sizeof f);
f[s]=0;
vis[s]=1;
pq.push({f[s],s});
while(!pq.empty())
{
int t=pq.top().second;pq.pop();
vis[t]=1;
TF(i,t,y)
{
y=to[i];
if(vis[y]) continue;
if(f[y]>f[t]+val[i])
f[y]=f[t]+val[i],pq.push({f[y],y});
}
}
}
int main()
{
scanf("%lld%lld%lld",&n,&q,&s);
cnt=n;
build(1,1,n);
while(q--)
{
ll op,x,c,l,r;
scanf("%lld%lld",&op,&x);
if(op==1)
{
scanf("%lld%lld",&l,&c);
add(x,l,c);
}
if(op==2)
{
scanf("%lld%lld%lld",&l,&r,&c);
fixin(1,1,n,l,r,x,c);
}
if(op==3)
{
scanf("%lld%lld%lld",&l,&r,&c);
fixout(1,1,n,l,r,x,c);
}
}
dij(s);
_F(i,1,n)
{
if(f[i]>=0x3f3f3f3f3f3f3f3f)
printf("-1 ");
else
printf("%lld ",f[i]);
}
return 0;
}线段树维护扫描线
这个就没有什么好说的了，在接触边界时加入线段树，在离开边界时删除在线段树中的影响即可，对于面积与周长有不同求法
eg- P1856 [IOI1998] [USACO5.5] 矩形周长Picture
code
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
#include <bits/stdc++.h>
#define _F(x,y,z) for(int x=y;x<=z;x++)
#define F_(x,z,y) for(int x=z;x>=y;x--)
#define TF(x,y,z) for(int x=head[y],z;x;x=nex[x])
#define lson now<<1
#define rson now<<1|1
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;
typedef double dou;
typedef const int ci;
ci maxn=2e4+10;
struct ss
{
int y,x1,x2,op;
}a[maxn];
vector<vector<int> > v;
int n,ans,cnt,tr[maxn<<2],c[maxn<<2],la[maxn<<2],mn,cm;
bool cmp(ss a,ss b)
{
if(a.y==b.y)
return a.op>b.op;
return a.y<b.y;
}
void build(int now,int l,int r)
{
tr[now]=0;c[now]=(r-l+1),la[now]=0;
if(l==r) return ;
build(lson,l,mid);
build(rson,mid+1,r);
}
void pd(int now)
{
if(la[now])
{
tr[lson]+=la[now];
tr[rson]+=la[now];
la[lson]+=la[now];
la[rson]+=la[now];
la[now]=0;
}
}
void fix(int now,int l,int r,int x,int y,int k)
{
if(x<=l&&r<=y)
{
tr[now]+=k;
la[now]+=k;
return ;
}
pd(now);
if(x<=mid)
fix(lson,l,mid,x,y,k);
if(y>mid)
fix(rson,mid+1,r,x,y,k);
tr[now]=min(tr[lson],tr[rson]);
c[now]=0;
if(tr[now]==tr[lson])
c[now]+=c[lson];
if(tr[now]==tr[rson])
c[now]+=c[rson];
return ;
}
void query(int now,int l,int r,int x,int y)
{
if(x<=l&&r<=y)
{
if(mn>tr[now])
mn=tr[now],cm=c[now];
else if(mn==tr[now])
cm+=c[now];
return ;
}
pd(now);
if(x<=mid)
query(lson,l,mid,x,y);
if(y>mid)
query(rson,mid+1,r,x,y);
}
void solve()
{
build(1,1,maxn-10);
cnt=0;
_F(i,0,n-1)
{
int x1=v[i][0],Y1=v[i][1],x2=v[i][2],y2=v[i][3];
a[++cnt]=ss{Y1,x1,x2,1};
a[++cnt]=ss{y2,x1,x2,-1};
}
sort(a+1,a+1+cnt,cmp);
_F(i,1,cnt)
{
if(a[i].op==1)
{
mn=1e9,cm=0;
query(1,1,maxn-10,a[i].x1,a[i].x2-1);
if(!mn)
ans+=cm;
}
fix(1,1,maxn-10,a[i].x1,a[i].x2-1,a[i].op);
if(a[i].op==-1)
{
mn=1e9,cm=0;
query(1,1,maxn-10,a[i].x1,a[i].x2-1);
if(!mn)
ans+=cm;
}
}
}
int main()
{
scanf("%d",&n);
_F(i,1,n)
{
int x1,Y1,x2,y2;
scanf("%d%d%d%d",&x1,&Y1,&x2,&y2);
x1+=10001;Y1+=10001,x2+=10001,y2+=10001;
v.push_back({x1,Y1,x2,y2});
}
solve();
_F(i,0,n-1)
{
swap(v[i][0],v[i][1]);
swap(v[i][2],v[i][3]);
}
solve();
printf("%d",ans);
return 0;
}线段树上二分
额，我觉得这个名字好像怪怪的。看这个名字总是不知道他要干什么。但实际上就是，到达一个线段树上的节点后，根据线段树左右儿子的信息进入不同子树统计答案。
变种挺多的，还需要牢牢掌握。
例子就是典型的查询第 大 / 第 小。
code
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
#include <bits/stdc++.h>
#define _F(x,y,z) for(int x=y;x<=z;x++)
#define F_(x,y,z) for(int x=z;x>=y;x--)
#define TF(x,y,z) for(int x=head[y],z;x;x=nex[x])
using namespace std;
typedef long long ll;
typedef double dou;
typedef const int ci;
ci maxn=3e5+10,N=100001;
int n,mi,tr[maxn<<2],la[maxn<<2],lazy,cnt;
#define lson (now<<1)
#define rson (now<<1|1)
#define mid ((l+r)>>1)
void pd(int now)
{
if(la[now])
{
la[lson]=la[now];
la[rson]=la[now];
tr[lson]=0;
tr[rson]=0;
la[now]=0;
}
}
void change(int now,int l,int r,int x,int t)
{
if(l==r)
{
tr[now]++;
return ;
}
pd(now);
if(x<=mid)
change(lson,l,mid,x,t);
else
change(rson,mid+1,r,x,t);
tr[now]=tr[lson]+tr[rson];
}
void fix(int now,int l,int r,int x,int y)
{
if(x<=l&&r<=y)
{
la[now]=1;
tr[now]=0;
return ;
}
pd(now);
if(x<=mid)
fix(lson,l,mid,x,y);
if(y>mid)
fix(rson,mid+1,r,x,y);
tr[now]=tr[lson]+tr[rson];
}
int ask(int now,int l,int r,int x)
{
if(l==r)
{
return l;
}
pd(now);
if(x>tr[rson])//重点在这里
return ask(lson,l,mid,x-tr[rson]);
else
return ask(rson,mid+1,r,x);
}
int main()
{
scanf("%d%d",&n,&mi);
mi+=N;
_F(i,1,n)
{
char a[6];
int x;
scanf("%s%d",a+1,&x);
if(a[1]=='I')
{
x+=N;
if(x>=mi)
{
cnt++;
change(1,1,maxn-10,x-lazy,1);
fix(1,1,maxn-10,1,mi-lazy-1);
}
}
else if(a[1]=='S')
{
lazy-=x;
if(mi-lazy-1>0)
fix(1,1,maxn-10,1,mi-lazy-1);
}
else if(a[1]=='A')
{
lazy+=x;
}
else
{
if(x<=tr[1])
printf("%d\n",ask(1,1,maxn-10,x)+lazy-N);
else
puts("-1");
}
}
fix(1,1,maxn-10,1,mi-lazy-1);
printf("%d",cnt-tr[1]);
return 0;
}线段树维护单调栈
学习这个之前建议先掌握线段树上二分
这个知识点变化较多，我们以一道典中典为例
典中典.P4198 楼房重建
我们在线段树中再设一个 tr[i] 来表示， i 管辖的这段区间单调的个数，对于两个区间，我们首先保留左区间，然后在在右子树上二分即可。
代码我还没写（
这个题我就不在这里推式子了，自己去看题解罢。
代码好像还挺少（
code
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
#include <bits/stdc++.h>
#define _F(x,y,z) for(int x=y;x<=z;x++)
#define F_(x,z,y) for(int x=z;x>=y;x--)
#define TF(x,y,z) for(int x=head[y],z;x;x=nex[x])
#define lson now<<1
#define rson now<<1|1
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;
typedef double dou;
typedef const int ci;
ci maxn=2e6+10;
int n,m,p,mx[maxn<<2],tr[maxn<<2],a[maxn],ans;
//重点在这里
int query(int now,int l,int r,int x)
{
if(l==r)
{
if(mx[now]>x)
return l+x;
return 1145141919;
}
if(mx[rson]>x)
return min(tr[now],query(rson,mid+1,r,x));
return query(lson,l,mid,x);
}
void pu(int now,int l,int r)
{
mx[now]=max(mx[lson],mx[rson]);
tr[now]=query(lson,l,mid,mx[rson]);
}
//以下就是普通线段树
void build(int now,int l,int r)
{
if(l==r)
{
mx[now]=a[l]-l;
return ;
}
build(lson,l,mid),build(rson,mid+1,r);
pu(now,l,r);
}
void change(int now,int l,int r,int x,int k)
{
if(l==r)
{
mx[now]=k-l;
return ;
}
if(x<=mid)
change(lson,l,mid,x,k);
else
change(rson,mid+1,r,x,k);
pu(now,l,r);
}
int main()
{
scanf("%d%d%d",&n,&m,&p);
_F(i,1,n)
scanf("%d",&a[i]);
build(1,1,n);
ans=query(1,1,n,mx[1]-n)+n;
printf("%d\n",ans);
while(m--)
{
int x,y;
scanf("%d%d",&x,&y);
if(p)
x^=ans,y^=ans;
change(1,1,n,x,y);
ans=query(1,1,n,mx[1]-n)+n;
printf("%d\n",ans);
}
return 0;
}