树链剖分专题2

自用笔记算法

树链剖分专题2

专题2主要包括：

1.线段树复杂合并(颜色段 差值 lcis)
2.线段树维护子树
3.颜色转换二进制维护

bzoj 2243

题目要求

给定一棵有n个节点的无根树和m个操作，操作有2类：
1、将节点a到节点b路径上所有点都染成颜色c；
2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。
请你写一个程序依次完成这m个操作。

第一行包含2个整数n和m，分别表示节点数和操作数；
第二行包含n个正整数表示n个节点的初始颜色
下面 行每行包含两个整数x和y，表示x和y之间有一条无向边。
下面 行每行描述一个操作：
“C a b c”表示这是一个染色操作，把节点a到节点b路径上所有点（包括a和b）都染成颜色c；
“Q a b”表示这是一个询问操作，询问节点a到节点b（包括a和b）路径上的颜色段数量。

对于每个询问操作，输出一行答案。

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100050
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
int n,q,step;
int c[maxn];
int sz[maxn],dep[maxn],fa[maxn],son[maxn];
int id[maxn],top[maxn];
int val[maxn];
struct T{
    int lc,rc,lazy,num;
    T(){
        lc=rc=-1;  
        num=0;  
    }  
}tree[maxn<<2];
vector<int>e[maxn];
void init(){
    for(int i=0;i<=n;i++) e[i].clear();
    mm(sz,0),mm(dep,0),mm(fa,0),mm(son,0);
    mm(id,0),mm(top,0),mm(val,0),mm(c,0);
    step=0;
}
void dfs1(int x,int f,int deep){
    sz[x]=1,fa[x]=f,son[x]=0,dep[x]=deep;
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(next==f) continue;
        dfs1(next,x,deep+1);
        sz[x]+=sz[next];
        if(sz[son[x]]<sz[next]) son[x]=next;
    }
}
void dfs2(int x,int tp){
    top[x]=tp;
    id[x]=++step;
    val[id[x]]=x;
    if(son[x]) dfs2(son[x],tp);
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(next==fa[x] || next==son[x]) continue;
        dfs2(next,next);
    }
}
T merge(T a,T b){
	if(a.num==0) return b;
	if(b.num==0) return a;
	T temp;
	temp.lc=a.lc;
	temp.rc=b.rc;
	if(a.rc==b.lc) temp.num=a.num+b.num-1;
	else temp.num=a.num+b.num;
	return temp;
}
void push_up(int rt){
    tree[rt].lc=tree[rt<<1].lc;
    tree[rt].rc=tree[rt<<1|1].rc;
    tree[rt].num=tree[rt<<1].num+tree[rt<<1|1].num;
    if(tree[rt<<1].rc==tree[rt<<1|1].lc) tree[rt].num--;
}
void push_down(int rt){
	if(tree[rt].lazy!=-1){
		tree[rt<<1].lazy=tree[rt].lazy;
		tree[rt<<1|1].lazy=tree[rt].lazy;
		tree[rt<<1].num=tree[rt<<1|1].num=1;
		tree[rt<<1].lc=tree[rt<<1].rc=tree[rt<<1|1].lc=tree[rt<<1|1].rc=tree[rt].lazy;
		tree[rt].lazy=-1;
	}
}
void build(int rt,int l,int r){
	tree[rt].lazy=-1;
    if(l==r){
    	tree[rt].lc=c[val[l]];
    	tree[rt].rc=c[val[l]];
    	tree[rt].num=1;
    	return;
	}
	int mid=(l+r)>>1;
	build(lson);
	build(rson);
	push_up(rt);
}
void update(int rt,int l,int r,int L,int R,int x){
    if(l>=L && r<=R){
    	tree[rt].lazy=x;
    	tree[rt].lc=tree[rt].rc=x;
    	tree[rt].num=1;
		return;
	}
	push_down(rt);
	int mid=(l+r)>>1;
	if(mid>=R) update(lson,L,R,x);
	else if(mid<L) update(rson,L,R,x);
	else{
		update(lson,L,R,x);
		update(rson,L,R,x);
	}
	push_up(rt);
}
T query(int rt,int l,int r,int L,int R){
	if(l>=L && r<=R) return tree[rt];
	push_down(rt);
	int mid=(l+r)>>1;
	if(mid>=R) return query(lson,L,R);
	else if(mid<L) return query(rson,L,R);
	else return merge(query(lson,L,R),query(rson,L,R));
}
void change(int x,int y,int val){
	while(top[x]!=top[y]){  
        if(dep[top[x]]<dep[top[y]]) swap(x,y);  
        update(1,1,n,id[top[x]],id[x],val);  
        x=fa[top[x]];  
    }  
    if(dep[x]>dep[y]) swap(x,y);  
    update(1,1,n,id[x],id[y],val);  
}
int queryco(int x,int y){
	T l,r;
	while(top[x]!=top[y]){  
        if(dep[top[x]]<dep[top[y]]){
        	swap(x,y);
        	swap(l,r);
		}
        l=merge(query(1,1,n,id[top[x]],id[x]),l);    
        x=fa[top[x]];
    }  
    if(dep[x]>dep[y]){
    	swap(x,y);
    	swap(l,r);
	}  
    r=merge(query(1,1,n,id[x],id[y]),r);
    int ans=0;
	if(l.lc==r.lc) ans=l.num+r.num-1;
	else ans=l.num+r.num;
	return ans;
}
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d%d",&n,&q)!=EOF){
		init();
		for(int i=1;i<=n;i++) scanf("%d",&c[i]);
		for(int i=1;i<n;i++){
			int u,v;
			scanf("%d%d",&u,&v);
			e[u].push_back(v);
			e[v].push_back(u);
		}
		dfs1(1,0,0);
		dfs2(1,1);
		build(1,1,n);
		while(q--){
			char op[5];
			scanf("%s",op);
			if(op[0]=='C'){
				int x,y,k;
				scanf("%d%d%d",&x,&y,&k);
				change(x,y,k);
			}
			else{
				int x,y;
				scanf("%d%d",&x,&y);
				printf("%d\n",queryco(x,y));
			}
		}
	}
    return 0;
}

思路

用线段树维护颜色段 注意合并的时候若l的右端点和r的左端点相同 那么相加的总段数-1
注意：
1.本题颜色可以取到0 所以lazy的初始化要为-1而不能是0
2.结构体需要初始化l r和num 否则quertco里的T l和r会出错

HDU 5052

题目要求

一棵树，每个结点有个初始的权值，点的权值代表在该点的鸡肉的价格。
对于一个询问X, Y, V。
找到X到Y的路径，可以选择在路径上一个点I买鸡肉，然后在点J卖掉，要求J必须在I之后访问。
那么你就可以赚取差价，问最大差价是多少。然后这条路径上的点的权值全部增加V。

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 50050
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
int n,q,step;
int c[maxn];
int sz[maxn],dep[maxn],fa[maxn],son[maxn];
int id[maxn],top[maxn];
int val[maxn];
struct T{
    int Max,Min,mxl,mxr,lazy;
}tree[maxn<<2];
vector<int>e[maxn];
void init(){
    for(int i=0;i<=n;i++) e[i].clear();
    mm(sz,0),mm(dep,0),mm(fa,0),mm(son,0);
    mm(id,0),mm(top,0),mm(val,0),mm(c,0);
    step=0;
}
void dfs1(int x,int f,int deep){
    sz[x]=1,fa[x]=f,son[x]=0,dep[x]=deep;
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(next==f) continue;
        dfs1(next,x,deep+1);
        sz[x]+=sz[next];
        if(sz[son[x]]<sz[next]) son[x]=next;
    }
}
void dfs2(int x,int tp){
    top[x]=tp;
    id[x]=++step;
    val[id[x]]=x;
    if(son[x]) dfs2(son[x],tp);
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(next==fa[x] || next==son[x]) continue;
        dfs2(next,next);
    }
}
T merge(T a,T b){
	a.mxl=max(max(a.mxl,b.mxl),b.Max-a.Min);
	a.mxr=max(max(a.mxr,b.mxr),a.Max-b.Min);
	a.Max=max(a.Max,b.Max);
	a.Min=min(a.Min,b.Min);
	return a;
}
void push_up(int rt){
    tree[rt].mxl=max(max(tree[rt<<1].mxl,tree[rt<<1|1].mxl),tree[rt<<1|1].Max-tree[rt<<1].Min);
    tree[rt].mxr=max(max(tree[rt<<1].mxr,tree[rt<<1|1].mxr),tree[rt<<1].Max-tree[rt<<1|1].Min);
    tree[rt].Max=max(tree[rt<<1].Max,tree[rt<<1|1].Max);
    tree[rt].Min=min(tree[rt<<1].Min,tree[rt<<1|1].Min);
}
void push_down(int rt){
	if(tree[rt].lazy){
		tree[rt<<1].Max+=tree[rt].lazy;
		tree[rt<<1|1].Max+=tree[rt].lazy;
		tree[rt<<1].Min+=tree[rt].lazy;
		tree[rt<<1|1].Min+=tree[rt].lazy;
		tree[rt<<1].lazy+=tree[rt].lazy;
		tree[rt<<1|1].lazy+=tree[rt].lazy;
		tree[rt].lazy=0;
	}
}  
void build(int rt,int l,int r){
	tree[rt].lazy=0;
	if(l==r){
		tree[rt].Max=tree[rt].Min=c[val[l]];
		tree[rt].mxl=tree[rt].mxr=0;
		return;
	}
	int mid=(l+r)>>1;
	build(lson);
	build(rson);
	push_up(rt);
}
void update(int rt,int l,int r,int L,int R,int x){
    if(l>=L && r<=R){
    	tree[rt].lazy+=x;
    	tree[rt].Max+=x;
    	tree[rt].Min+=x;
    	return;
	} 
	push_down(rt);
	int mid=(l+r)>>1;
	if(mid>=R) update(lson,L,R,x);
	else if(mid<L) update(rson,L,R,x);
	else update(lson,L,R,x),update(rson,L,R,x);
	push_up(rt);
}
T query(int rt,int l,int r,int L,int R){
	if(l>=L && r<=R) return tree[rt];
	push_down(rt);
	int mid=(l+r)>>1;
	if(mid>=R) return query(lson,L,R);
	else if(mid<L) return query(rson,L,R);
	else return merge(query(lson,L,R),query(rson,L,R));
}
void check(T& a,T& b){
	if(a.Min==0){
		a=b;
		return;
	}
	a.mxl=max(max(a.mxl,b.mxl),a.Max-b.Min);
	a.mxr=max(max(a.mxr,b.mxr),b.Max-a.Min);
	a.Max=max(a.Max,b.Max);
	a.Min=min(a.Min,b.Min);
}
int Query(int L,int R,int k){
	int ans=0;
	T ans1,ans2;
	ans1.lazy=-1,ans1.Max=ans1.Min=ans1.mxl=ans1.mxr=0;
	ans2.lazy=1,ans2.Max=ans2.Min=ans2.mxl=ans2.mxr=0;
    while(top[L]!=top[R]){
        if(dep[top[L]]<dep[top[R]]) swap(L,R),swap(ans1,ans2);
		int tp=ans1.lazy;
		T temp=query(1,1,n,id[top[L]],id[L]);
		check(ans1,temp);
		ans1.lazy=tp;
		update(1,1,n,id[top[L]],id[L],k);
        L=fa[top[L]];
    }
    if(id[L]>id[R]) swap(L,R),swap(ans1,ans2);
    int tp=ans2.lazy;
    T temp=query(1,1,n,id[L],id[R]);
    check(ans2,temp);
    ans2.lazy=tp;
    if(ans1.lazy==1) swap(ans1,ans2);
    update(1,1,n,id[L],id[R],k);
    ans=max(ans1.mxr,ans2.mxl);
    if(ans1.Min) ans=max(ans,ans2.Max-ans1.Min);
    return ans;
} 
int main(){
//	freopen("input.txt","r",stdin);
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		init();
		for(int i=1;i<=n;i++) scanf("%d",&c[i]);
		for(int i=1;i<n;i++){
			int u,v;
			scanf("%d%d",&u,&v);
			e[u].push_back(v);
			e[v].push_back(u);
		}
		dfs1(1,0,0);
		dfs2(1,1);
		build(1,1,n);
		int q;
		scanf("%d",&q);
		while(q--){
			int x,y,k;
			scanf("%d%d%d",&x,&y,&k);
			printf("%d\n",Query(x,y,k));
		}
	}
    return 0;
}

思路

这道题，首先考虑一条链的版本，我们用线段树来维护，先从区间合并来考虑。
对于当前结点，那么结点的最优值肯定来自于左孩子和右孩子的最优值，以及区间合并的最优值。
区间合并的时候，我们肯定是在左孩子的区间买，在右孩子的区间卖，最大差值肯定是右孩子的最大值-左孩子的最小值。
区间合并搞定了。更新操作也很容易，加个懒惰标记，由于区间内全部加上V值，对于区间内的差价是没有影响的，所以直接累加到标记上就可以。
那么来到这题，变成多条链的合并。我们会发现，如果是从X到Y的方向，求解方法同上。
但是如果我们是Y到X的方向，我们应该反过来，即最大差值=左孩子的最大值-右孩子的最小值。

HDU 3308

题目要求

本题虽然不是树链剖分 但是是建立在下一题的基础上
一条线段 给出点权 两种操作：
1.修改点权
2.求出区间l-r内的lcis(最长连续上升子序列)

参考AC代码

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 maxn 100050
#define mm(a,b) memset(a,b,sizeof(a))
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
int lsum[maxn<<2],rsum[maxn<<2],sum[maxn<<2];
int num[maxn];
int n,q;
void push_up(int rt,int l,int r){
	lsum[rt]=lsum[rt<<1];
	rsum[rt]=rsum[rt<<1|1];
	sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);
	int mid=(l+r)>>1;
	if(num[mid]<num[mid+1]){
		if(lsum[rt]==(mid-l+1)) lsum[rt]+=lsum[rt<<1|1];
		if(rsum[rt]==(r-mid)) rsum[rt]+=rsum[rt<<1];
		sum[rt]=max(sum[rt],rsum[rt<<1]+lsum[rt<<1|1]);
	}
}
void build(int rt,int l,int r){
	if(l==r){
		lsum[rt]=rsum[rt]=sum[rt]=1;
		return;
	}
	int mid=(l+r)>>1;
	build(lson);
	build(rson);
	push_up(rt,l,r);
}
void update(int rt,int l,int r,int x,int k){
	if(l==r){
		num[l]=k;
		return;
	}
	int mid=(l+r)>>1;
	if(mid>=x) update(lson,x,k);
	else update(rson,x,k);
	push_up(rt,l,r);
}
int query(int rt,int l,int r,int L,int R){
	if(l>=L && r<=R) return sum[rt];
	int mid=(l+r)>>1;
	if(mid>=R) return query(lson,L,R);
	else if(mid<L) return query(rson,L,R);
	else{
		int x1=query(lson,L,R);
		int x2=query(rson,L,R);
		int ans=max(x1,x2);
		if(num[mid]<num[mid+1]){
			ans=max(ans,min(rsum[rt<<1],mid-L+1)+min(lsum[rt<<1|1],R-mid));
		}
		return ans;
	}
}
int main(){
//	freopen("input.txt","r",stdin);
	int t; scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&q);
		for(int i=1;i<=n;i++) scanf("%d",&num[i]);
		build(1,1,n);
		while(q--){
			char op; cin>>op;
			if(op=='Q'){
				int x,y;
				scanf("%d%d",&x,&y);
				x++,y++;
				printf("%d\n",query(1,1,n,x,y));
			}
			else{
				int x,y;
				scanf("%d%d",&x,&y);
				x++;
				update(1,1,n,x,y);
			}
		}
	}
	return 0;
}

思路

线段树维护lcis
lsum表示左端点向右延伸的最大值 rsum表示右端点向左延伸的最大值
sum表示区间的最大值
注意pushup的合并操作即可 判断mid处是否可以衔接
下标从0开始 方便计算点的索引++
query里的合并注意mid-L+1 R-mid而不是l和r

HDU 4718

题目要求

本题建立在上一题的基础上 求树上两点间的lcis

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100050
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
int n,q,step;
int c[maxn];
int sz[maxn],dep[maxn],fa[maxn],son[maxn];
int id[maxn],top[maxn];
int val[maxn];
struct T{
	int l,r;
    int lval,rval;
	int LL,LR,RL,RR;
	int len,ren;
    T(){
    	lval=rval=0;
    	LL=LR=RL=RR=0;
    	len=ren=0;
	}
}tree[maxn<<2];
vector<int>e[maxn];
void init(){
    for(int i=0;i<=n;i++) e[i].clear();
    mm(sz,0),mm(dep,0),mm(fa,0),mm(son,0);
    mm(id,0),mm(top,0),mm(val,0),mm(c,0);
    step=0;
}
void dfs1(int x,int f,int deep){
    sz[x]=1,fa[x]=f,son[x]=0,dep[x]=deep;
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(next==f) continue;
        dfs1(next,x,deep+1);
        sz[x]+=sz[next];
        if(sz[son[x]]<sz[next]) son[x]=next;
    }
}
void dfs2(int x,int tp){
    top[x]=tp;
    id[x]=++step;
    val[id[x]]=x;
    if(son[x]) dfs2(son[x],tp);
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(next==fa[x] || next==son[x]) continue;
        dfs2(next,next);
    }
}
T merge(T a,T b){
	if(b.len==0) return a;
	T temp=a;
	temp.rval=b.rval;
	temp.r=b.r;
	temp.len=max(a.len,b.len);
	temp.ren=max(a.ren,b.ren);
	if(a.LR==a.r-a.l+1 && a.rval<b.lval) temp.LR=a.LR+b.LR;
	else temp.LR=a.LR;
	if(a.LL==a.r-a.l+1 && a.rval>b.lval) temp.LL=a.LL+b.LL;
	else temp.LL=a.LL;
	if(b.RL==b.r-b.l+1 && a.rval>b.lval) temp.RL=b.RL+a.RL;
	else temp.RL=b.RL;
	if(b.RR==b.r-b.l+1 && a.rval<b.lval) temp.RR=b.RR+a.RR;
	else temp.RR=b.RR;
	temp.len=max(temp.len,temp.LR);
	temp.len=max(temp.len,temp.RR);
	temp.ren=max(temp.ren,temp.RL);
	temp.ren=max(temp.ren,temp.LL);
	if(a.rval<b.lval) temp.len=max(temp.len,a.RR+b.LR);
	if(a.rval>b.lval) temp.ren=max(temp.ren,a.RL+b.LL);
	return temp;
}
void build(int rt,int l,int r){
	tree[rt].l=l,tree[rt].r=r;
	if(l==r){
		tree[rt].lval=tree[rt].rval=c[val[l]];
		tree[rt].LL=tree[rt].LR=tree[rt].RL=tree[rt].RR=1;
		tree[rt].len=tree[rt].ren=1;
		return;
	}
	int mid=(l+r)>>1;
	build(lson);
	build(rson);
	tree[rt]=merge(tree[rt<<1],tree[rt<<1|1]);
}
T query(int rt,int l,int r,int L,int R){
	if(l>=L && r<=R) return tree[rt];
	int mid=(l+r)>>1;
	if(mid>=R) return query(lson,L,R);
	else if(mid<L) return query(rson,L,R);
	else return merge(query(lson,L,R),query(rson,L,R));
}
int Query(int x,int y){
	int ans=0,flag=0;
	T ans1,ans2;
	while(top[x]!=top[y]){  
        if(dep[top[x]]<dep[top[y]]) swap(x,y),swap(ans1,ans2),flag^=1;  
        ans1=merge(query(1,1,n,id[top[x]],id[x]),ans1);
        x=fa[top[x]];  
    }  
    if(dep[x]>dep[y]) swap(x,y),swap(ans1,ans2),flag^=1;
    ans2=merge(query(1,1,n,id[x],id[y]),ans2);
	if(flag) swap(ans1,ans2);
    ans=max(ans1.ren,ans2.len);
    if(ans1.lval<ans2.lval) ans=max(ans,ans1.LL+ans2.LR);
	return ans;  
}
int main(){
//	freopen("input.txt","r",stdin);
	int t;
	int f=0;
	scanf("%d",&t);
	while(t--){
		if(f) puts("");
		scanf("%d",&n);
		init();
		for(int i=1;i<=n;i++) scanf("%d",&c[i]);
		for(int i=2;i<=n;i++){
			int x;
			scanf("%d",&x);
			e[x].push_back(i);
			e[i].push_back(x);
		}
		dfs1(1,0,0);
		dfs2(1,1);
		build(1,1,n);
		scanf("%d",&q);
		cout<<"Case #"<<++f<<":"<<endl;
		while(q--){
			int u,v;
			scanf("%d%d",&u,&v);
			printf("%d\n",Query(u,v));
		}
	}
	return 0;
}

思路

树上的问题 用树链剖分转换成线性结构 就跟上题类似了
由于树链剖分向上爬的特殊性 需要继续2个方向的最大值 所以参数如下：
LL：左端点下降的最远距离
LR：左端点上升的最远距离
RL：右端点上升的最远距离
RR：右端点下降的最远距离
len：从左向右的最大长度
ren：从右向左的最大长度
同时为了merge的顺利实现 需要记录l和r两个边界的值
具体merge实现与上题类似

bzoj 4034

题目要求

有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个
操作，分为三种：
操作 1 ：把某个节点 x 的点权增加 a 。
操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。

第一行包含两个整数 N, M 。表示点数和操作数。接下来一行 N 个整数，表示树中节点的初始权值。接下来 N-1
行每行三个正整数 fr, to ， 表示该树中存在一条边 (fr, to) 。再接下来 M 行，每行分别表示一次操作。其中
第一个数表示该操作的种类（ 1-3 ） ，之后接这个操作的参数（ x 或者 x a ） 。

对于每个询问操作，输出该询问的答案。答案之间用换行隔开。

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100050
#define inf 0x3f3f3f3f
#define LL long long
#define mm(a,b) memset(a,b,sizeof(a))
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
int n,q,step;
int c[maxn];
int sz[maxn],dep[maxn],fa[maxn],son[maxn];
int in[maxn],out[maxn],top[maxn];
int val[maxn];
LL sum[maxn<<2],lazy[maxn<<2];
vector<int>e[maxn];
void init(){
    for(int i=0;i<=n;i++) e[i].clear();
    mm(sz,0),mm(dep,0),mm(fa,0),mm(son,0);
    mm(in,0),mm(out,0),mm(top,0),mm(val,0),mm(c,0);
    step=0;
}
void dfs1(int x,int f,int deep){
    sz[x]=1,fa[x]=f,son[x]=0,dep[x]=deep;
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(next==f) continue;
        dfs1(next,x,deep+1);
        sz[x]+=sz[next];
        if(sz[son[x]]<sz[next]) son[x]=next;
    }
}
void dfs2(int x,int tp){
    top[x]=tp;
    in[x]=++step;
    val[in[x]]=x;
    if(son[x]) dfs2(son[x],tp);
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(next==fa[x] || next==son[x]) continue;
        dfs2(next,next);
    }
    out[x]=step;
}
void push_up(int rt){
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void push_down(int rt,int l,int r){
    if(lazy[rt]){
        int mid=(l+r)>>1;
        lazy[rt<<1]+=lazy[rt];
        lazy[rt<<1|1]+=lazy[rt];
        sum[rt<<1]+=(mid-l+1)*(LL)lazy[rt];
        sum[rt<<1|1]+=(r-mid)*(LL)lazy[rt];
        lazy[rt]=0;
    }
}
void build(int rt,int l,int r){
    lazy[rt]=0;
    if(l==r){
        sum[rt]=(LL)c[val[l]];
        return;
    }
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
    push_up(rt);
}
void update(int rt,int l,int r,int L,int R,int k){
    if(l>=L && r<=R){
        sum[rt]+=(r-l+1)*(LL)k;
        lazy[rt]+=k;
        return;
    }
    push_down(rt,l,r);
    int mid=(l+r)>>1;
    if(mid>=L) update(lson,L,R,k);
    if(mid<R) update(rson,L,R,k);
    push_up(rt);
}
LL query(int rt,int l,int r,int L,int R){
    if(l>=L && r<=R) return sum[rt];
    push_down(rt,l,r);
    int mid=(l+r)>>1;
    LL sum=0;
    if(mid>=L) sum+=query(lson,L,R);
    if(mid<R) sum+=query(rson,L,R);
    return sum;
}
LL getsum(int x,int y){
    LL sum=0;
    while(top[x]!=top[y]){  
        if(dep[top[x]]<dep[top[y]]) swap(x,y);  
        sum+=query(1,1,n,in[top[x]],in[x]);  
        x=fa[top[x]];  
    }  
    if(dep[x]>dep[y]) swap(x,y);  
    sum+=query(1,1,n,in[x],in[y]);
    return sum;  
}
int main(){
//  freopen("input.txt","r",stdin);
    while(scanf("%d%d",&n,&q)!=EOF){
        init();
        for(int i=1;i<=n;i++) scanf("%d",&c[i]);
        for(int i=1;i<n;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            e[u].push_back(v);
            e[v].push_back(u);
        }
        dfs1(1,0,0);
        dfs2(1,1);
        build(1,1,n);
        while(q--){
            int op;
            scanf("%d",&op);
            if(op==1){
                int x,y;
                scanf("%d%d",&x,&y);
                update(1,1,n,in[x],in[x],y);
            }
            else if(op==2){
                int x,y;
                scanf("%d%d",&x,&y);
                update(1,1,n,in[x],out[x],y);
            }
            else{
                int x;
                scanf("%d",&x);
                printf("%lld\n",getsum(1,x));
            }
        }
    }
    return 0;
}

思路

由于有某节点到根节点的操作 这是一条链 所以使用树链剖分 也有子树的操作 在dfs2加入in和out数组求出dfs序去维护子树
注意开LL 并且本题是区间更新区间求和 sum需要加左右端点区间内的每一个值 所以注意pushdown和sum的写法

bzoj 4196

题目要求

你决定设计你自己的软件包管理器。不可避免地，你要解决软件包之间的依赖问题。如果软件包A依赖软件包B，那么安装软件包A以前，必须先安装软件包B。
同时，如果想要卸载软件包B，则必须卸载软件包A。现在你已经获得了所有的软件包之间的依赖关系。而且，由于你之前的工作，除0号软件包以外，在你的管理器
当中的软件包都会依赖一个且仅一个软件包，而0号软件包不依赖任何一个软件包。依赖关系不存在环（若有m(m≥2)个软件包A1,A2,A3,…,Am，其中A1依赖A2，A2依赖A3
，A3依赖A4，……，Am−1依赖Am，而Am依赖A1，则称这m个软件包的依赖关系构成环），当然也不会有一个软件包依赖自己。
现在你要为你的软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态
（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。注意，安装一个已安装的软件包，
或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为0。

输入文件的第1行包含1个正整数n，表示软件包的总数。软件包从0开始编号。
随后一行包含n−1个整数，相邻整数之间用单个空格隔开，分别表示1,2,3,…,n−2,n−1号软件包依赖的软件包的编号。
接下来一行包含1个正整数q，表示询问的总数。
之后q行，每行1个询问。询问分为两种：
installx：表示安装软件包x
uninstallx：表示卸载软件包x
你需要维护每个软件包的安装状态，一开始所有的软件包都处于未安装状态。对于每个操作，你需要输出这步操作会改变多少个软件包的安装状态，
随后应用这个操作（即改变你维护的安装状态）。

输出文件包括q行。
输出文件的第i行输出1个整数，为第i步操作中改变安装状态的软件包数。

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100050
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
int n,q,step;
int sz[maxn],dep[maxn],fa[maxn],son[maxn];
int in[maxn],out[maxn],top[maxn];
int sum[maxn<<2],lazy[maxn<<2];
vector<int>e[maxn];
void init(){
    for(int i=0;i<=n;i++) e[i].clear();
    mm(sz,0),mm(dep,0),mm(fa,0),mm(son,0);
    mm(in,0),mm(out,0),mm(top,0);
    step=0;
}
void dfs1(int x,int f,int deep){
    sz[x]=1,fa[x]=f,son[x]=0,dep[x]=deep;
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(next==f) continue;
        dfs1(next,x,deep+1);
        sz[x]+=sz[next];
        if(sz[son[x]]<sz[next]) son[x]=next;
    }
}
void dfs2(int x,int tp){
    top[x]=tp;
    in[x]=++step;
    if(son[x]) dfs2(son[x],tp);
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(next==fa[x] || next==son[x]) continue;
        dfs2(next,next);
    }
    out[x]=step;
}
void push_up(int rt){
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void push_down(int rt,int l,int r){
	if(lazy[rt]!=-1){
		int mid=(l+r)>>1;
		lazy[rt<<1]=lazy[rt];
		lazy[rt<<1|1]=lazy[rt];
		if(lazy[rt]) sum[rt<<1]=mid-l+1,sum[rt<<1|1]=r-mid;
		else sum[rt<<1]=sum[rt<<1|1]=0;
		lazy[rt]=-1;
	}
}
void build(int rt,int l,int r){
	lazy[rt]=-1;
	if(l==r){
		sum[rt]=0;
		return;
	}
	int mid=(l+r)>>1;
	build(lson);
	build(rson);
	push_up(rt);
}
void update(int rt,int l,int r,int L,int R,int k){
	if(l>=L && r<=R){
		lazy[rt]=k;
		if(k) sum[rt]=r-l+1;
		else sum[rt]=0;
		return;
	}
	push_down(rt,l,r);
	int mid=(l+r)>>1;
	if(mid>=L) update(lson,L,R,k);
	if(mid<R) update(rson,L,R,k);
	push_up(rt);
}
int query(int rt,int l,int r,int L,int R){
	if(l>=L && r<=R) return sum[rt];
	push_down(rt,l,r);
	int mid=(l+r)>>1;
	int ans=0;
	if(mid>=L) ans+=query(lson,L,R);
	if(mid<R) ans+=query(rson,L,R);
	return ans;
}
int solve1(int x,int y){
	int ans=0;
	while(top[x]!=top[y]){  
        if(dep[top[x]]<dep[top[y]]) swap(x,y);  
        ans+=in[x]-in[top[x]]+1-query(1,1,n,in[top[x]],in[x]);
		update(1,1,n,in[top[x]],in[x],1);  
        x=fa[top[x]];  
    }
    if(dep[x]>dep[y]) swap(x,y);
	ans+=in[y]-in[x]+1-query(1,1,n,in[x],in[y]); 
    update(1,1,n,in[x],in[y],1);  
	return ans;
}
int solve2(int x){
	int ans=query(1,1,n,in[x],out[x]);
	update(1,1,n,in[x],out[x],0);
	return ans;
}
char op[15];
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d",&n)!=EOF){
		init();
		for(int i=2;i<=n;i++){
			int x;
			scanf("%d",&x);
			x++;
			e[x].push_back(i);
			e[i].push_back(x);
		}
		dfs1(1,0,0);
		dfs2(1,1);
		build(1,1,n);
		scanf("%d",&q);
		while(q--){
			scanf("%s",op);
			if(op[0]=='i'){
				int x;
				scanf("%d",&x);
				x++;
				printf("%d\n",solve1(1,x));
			}
			else{
				int x;
				scanf("%d",&x);
				x++;
				printf("%d\n",solve2(x));
			}
		}
	}
	return 0;
}

思路

本题有2个操作：
初始时树上所有结点权值均为0；
安装操作将根到x结点的所有结点权值置为1，卸载操作将x结点的子树中所有结点权值置为0
前者显然树剖 后者显然dfs序 dfs序可在dfs2中求出
lazy用来表示是否安装的标记
由于结点编号从0开始 全部++方便计算
由于是区间求和问题 sum需要加上每一个点的值
solve1解决树剖更新 用总结点减去1的个数=0的个数 即为答案
solve2解决子树 query的1个数就是答案 注意2个操作后都有更新操作

本文标题:树链剖分专题2

文章作者:Hippopmonkey

发布时间:2017-08-24, 15:17:26

最后更新:2017-09-05, 21:40:25

原始链接:http://xuboming8.github.io/2017/08/24/熟练剖分专题2/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 树链剖分专题2
    1. 1.1. bzoj 2243
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. HDU 5052
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. HDU 3308
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. HDU 4718
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. bzoj 4034
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
    6. 1.6. bzoj 4196
      1. 1.6.1. 题目要求
      2. 1.6.2. 参考AC代码
      3. 1.6.3. 思路
|