树链剖分专题3

自用笔记算法

树链剖分专题3

本专题主要包括线段树的多过程处理
1.离线维护每个点涂颜色的过程 for 1e6个点 并维护每个点
2.动态开点维护(多颗线段树)
3.离线维护q次小于等于k的最大值

HDU 5029

题目要求

给你一颗节点数最多为1e5的树。然后是m(1e5)条操作
x y z。
就是把x到y路径上的所有点包括x,y图上x颜色。
最后要你输出，每个点被图的次数最多的颜色是那个。如果有多个输出z最小的那个z(1-1e5)。

参考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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define PB push_back
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int INF=(int)1e9+7;
const int maxn=100010;
int n,m,Ecnt,tot,head[maxn],pr[maxn];
int top[maxn],fa[maxn],son[maxn],sz[maxn],id[maxn],val[maxn],deep[maxn];
struct EE{
    int to,next;
    EE(){}
    EE(int to,int next):to(to),next(next){}
}edge[maxn*2];
inline void addedge(int a,int b){
    edge[Ecnt]=EE(b,head[a]);
    head[a]=Ecnt++;
}
void dfs1(int s,int pre,int d){
    deep[s]=d,fa[s]=pre,sz[s]=1,son[s]=-1;
    for(int i=head[s];~i;i=edge[i].next){
        int t=edge[i].to;
        if(t==pre) continue;
        dfs1(t,s,d+1);
		sz[s]+=sz[t];
        if(son[s]==-1 || sz[t]>sz[son[s]]) son[s]=t;
    }
}
void dfs2(int s,int rt){
    top[s]=rt;id[s]=++tot;val[tot]=s;
    if(son[s]==-1) return;
    dfs2(son[s],rt);
    for(int i=head[s];~i;i=edge[i].next){
        int t=edge[i].to;
        if(t==fa[s]||t==son[s]) continue;
        dfs2(t,t);
    }
}
vector<vector<int> >add,des;
void cal(int x,int y,int v){
    int f1=top[x],f2=top[y];
    while(f1!=f2){
        if(deep[f1]<deep[f2]){
            swap(f1,f2);swap(x,y);
        }
        add[id[f1]].PB(v);
        des[id[x]+1].PB(v);
        x=fa[f1];f1=top[x];
    }
    if(deep[x]>deep[y]) swap(x,y);
    add[id[x]].PB(v);
    des[id[y]+1].PB(v);
}
struct node{
    int MAX,id;
}tree[maxn<<2];
inline void pushup(int rt){
    if(tree[rt<<1].MAX>=tree[rt<<1|1].MAX){
        tree[rt].MAX=tree[rt<<1].MAX;
        tree[rt].id=tree[rt<<1].id;
    }
    else{
        tree[rt].MAX=tree[rt<<1|1].MAX;
        tree[rt].id=tree[rt<<1|1].id;
    }
}
void build(int l,int r,int rt){
    tree[rt].MAX=tree[rt].id=0;
    if(l==r){
        tree[rt].id=l;
        return;
    }
    int mid=l+r>>1;
    build(lson);
	build(rson);
}
void update(int x,int v,int l,int r,int rt){
    if(l==r){
        tree[rt].MAX+=v;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid) update(x,v,lson);
    else update(x,v,rson);
    pushup(rt);
}
int main(){
//	freopen("input.txt","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF){
        if(n==0 && m==0) break;
        memset(head,-1,sizeof head);
        Ecnt=0;
        for(int i=1;i<n;i++){
            int a,b;
			scanf("%d%d",&a,&b);
            addedge(a,b);addedge(b,a);
        }
        tot=0;
        dfs1(1,0,0);
		dfs2(1,1);
        add.clear(); des.clear();
        add.resize(maxn); des.resize(maxn);
        for(int i=0;i<m;i++){
            int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
            cal(a,b,c);
        }
        build(1,100000,1);
        memset(pr,0,sizeof pr);
        for(int i=1;i<=n;i++){
            for(int j=0,len=(int)add[i].size();j<len;j++){
                update(add[i][j],1,1,100000,1);
            }
            for(int j=0,len=(int)des[i].size();j<len;j++){
                update(des[i][j],-1,1,100000,1);
            }
            if(tree[1].MAX==0) pr[val[i]]=0;
            else pr[val[i]]=tree[1].id;
        }
        for(int i=1;i<=n;i++) printf("%d\n",pr[i]);
    }
    return 0;
}

思路

这题的输出，是每个点中的最多数字，但是是等全部处理完以后再输出。那我们就要考虑怎么来维护这个数据。我们可以想到，把这棵树进行树链剖分以后，
就可以理解成一条直线了，那这题就抽象成在直线上进行操作。我们可以考虑用线段树维护节点上的数字，每个节点表示这种数字有几个。
先考虑线段树最左边的节点，如果我们把覆盖到当前点的操作全部处理了，那么就能求出当前情况下，最多的数字是谁，然后等轮到每个操作的区间的
右区间的时候，再把这个点减去，就像一个从左到右的扫描线一样。这就是一个单点修改，求区间最值的线段树模型。那么我们保存下所有输入的操作，
处理成线段树上的操作，保存下来。因为[1,n]的编号分别对应了树上的节点，我们可以枚举1到n，表示n个节点，按照编号顺序从左到右来处理操作，
就可以求出当前情况下，最多的数字是多少。

bzoj 3531

题目要求

S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足
从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。
为了方便，我们用不同的正整数代表各种宗教， S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。
当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级总和或最大值。
在S国的历史上常会发生以下几种事件：
”CC x c”：城市x的居民全体改信了c教；
”CW x w”：城市x的评级调整为w;
”QS x y”：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级总和；
”QM x y”：一位旅行者从城市x出发，到城市y，并记下了途中留宿过
的城市的评级最大值。
由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。
为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。

输入的第一行包含整数N，Q依次表示城市数和事件数。
接下来N行，第i+l行两个整数Wi，Ci依次表示记录开始之前，城市i的
评级和信仰。
接下来N-1行每行两个整数x，y表示一条双向道路。
接下来Q行，每行一个操作，格式如上所述。

对每个QS和QM事件，输出一行，表示旅行者记下的数字。

参考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
#include<bits/stdc++.h>
#define maxn 100050
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
#define lson tree[rt].l,l,mid
#define rson tree[rt].r,mid+1,r
using namespace std;
int n,q,step,cnt;
int w[maxn],c[maxn];
int sz[maxn],dep[maxn],fa[maxn],son[maxn];
int id[maxn],top[maxn];
int root[maxn];
struct T{
	int l,r; 
    int sum,Max;
}tree[maxn*100];
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(root,0);
    mm(tree,0);
    step=0,cnt=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;
    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);
    }
}
void push_up(int rt){
	tree[rt].Max=max(tree[tree[rt].l].Max,tree[tree[rt].r].Max);
	tree[rt].sum=tree[tree[rt].l].sum+tree[tree[rt].r].sum;
}
void update(int &rt,int l,int r,int pos,int val){
	if(!rt) rt=++cnt;
	if(l==r){
		tree[rt].Max=tree[rt].sum=val;
		return;
	}
	int mid=(l+r)>>1;
	if(mid>=pos) update(lson,pos,val);
	else update(rson,pos,val);
	push_up(rt);
}
int querysum(int rt,int l,int r,int L,int R){
	if(!rt) return 0;
	if(l>=L && r<=R) return tree[rt].sum;
	int mid=(l+r)>>1;
	if(mid>=R) return querysum(lson,L,R);
	else if(mid<L) return querysum(rson,L,R);
	else return querysum(lson,L,R)+querysum(rson,L,R);
}
int querymx(int rt,int l,int r,int L,int R){
	if(!rt) return 0;
	if(l>=L && r<=R) return tree[rt].Max;
	int mid=(l+r)>>1;
	if(mid>=R) return querymx(lson,L,R);
	else if(mid<L) return querymx(rson,L,R);
	else return max(querymx(lson,L,R),querymx(rson,L,R));
}
int solvemx(int col,int L,int R){
    int ans=-inf;
    while(top[L]!=top[R]){
        if(dep[top[L]]<dep[top[R]]) swap(L,R);
        ans=max(ans,querymx(root[col],1,n,id[top[L]],id[L]));
        L=fa[top[L]];
    }
    if(id[L]>id[R]) swap(L,R);
    ans=max(ans,querymx(root[col],1,n,id[L],id[R]));
    return ans;
}
int solvesum(int col,int L,int R){
    int sum=0;
    while(top[L]!=top[R]){
        if(dep[top[L]]<dep[top[R]]) swap(L,R);
        sum+=querysum(root[col],1,n,id[top[L]],id[L]);
        L=fa[top[L]];
    }
    if(id[L]>id[R]) swap(L,R);
    sum+=querysum(root[col],1,n,id[L],id[R]);
    return sum;
}
char op[10];
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d%d",&n,&q)!=EOF){
		init();
		for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&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);
		for(int i=1;i<=n;i++) update(root[c[i]],1,n,id[i],w[i]);
		while(q--){
			scanf("%s",op);
			if(op[0]=='C'){
				if(op[1]=='C'){
					int x,y;
					scanf("%d%d",&x,&y);
					update(root[c[x]],1,n,id[x],0);
					c[x]=y;
					update(root[c[x]],1,n,id[x],w[x]);
				}
				else{
					int x,y;
					scanf("%d%d",&x,&y);
					update(root[c[x]],1,n,id[x],y);
					w[x]=y;
				}
			}
			else{
				if(op[1]=='S'){
					int x,y;
					scanf("%d%d",&x,&y);
					printf("%d\n",solvesum(c[x],x,y));
				}
				else{
					int x,y;
					scanf("%d%d",&x,&y);
					printf("%d\n",solvemx(c[x],x,y));
				}
			}
		}
	}
	return 0;
}

思路

线段树动态开点(多颗)
参考题目地址
因为宗教数量只有10^5，我们可以树链剖分完对于每一个宗教建立线段树
接着就是对每个宗教的维护线段树过程 线段树动态开点+树剖即可
注意solvesum和solvemx里的rt是root[col] col=c[x]
以及cc操作需要把原来的那些线段树x位置清零+新位置update更新

HDU 3804

题目要求

给出一棵树，询问从1到x路径上小于等于y的最大值
q次询问

参考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
#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 id[maxn],top[maxn];
int ans[maxn];
struct node{
	int to,w;
	node(int to,int w):to(to),w(w){}
};
struct edge{
	int u,v,w;
	bool operator < (const edge& x) const{
		return w<x.w;
	}
}ed[maxn];
struct Q{
	int x,y;
	int index;
	bool operator < (const Q& a) const{
		return y<a.y;
	}
}qu[maxn];
int Max[maxn<<2];
vector<node>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(ans,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].to;
        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;
    if(son[x]) dfs2(son[x],tp);
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i].to;
        if(next==fa[x] || next==son[x]) continue;
        dfs2(next,next);
    }
}
void push_up(int rt){
	Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);
}
void build(int rt,int l,int r){
	Max[rt]=-1;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(lson);
	build(rson);
}
void update(int rt,int l,int r,int pos,int val){
	if(l==r){
		Max[rt]=val;
		return;
	}
	int mid=(l+r)>>1;
	if(mid>=pos) update(lson,pos,val);
	else update(rson,pos,val);
	push_up(rt);
}
int query(int rt,int l,int r,int L,int R){
	if(l>=L && r<=R) return Max[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 max(query(lson,L,R),query(rson,L,R));
}
int querymx(int x,int y){
	int ans=-1;
	while(top[x]!=top[y]){  
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
		ans=max(ans,query(1,1,n,id[top[x]],id[x]));
        x=fa[top[x]];  
    } 
    if(x==y) return ans;
    if(dep[x]>dep[y]) swap(x,y);
    ans=max(ans,query(1,1,n,id[son[x]],id[y]));
	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++){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			ed[i].u=u,ed[i].v=v,ed[i].w=w;
			e[u].push_back(node(v,w));
			e[v].push_back(node(u,w));	
		}
		dfs1(1,0,0);
		dfs2(1,1);
		sort(ed+1,ed+n);
		build(1,1,n);
		scanf("%d",&q);
		for(int i=1;i<=q;i++){
			int x,y;
			scanf("%d%d",&x,&y);
			qu[i].x=x,qu[i].y=y,qu[i].index=i;
		}
		sort(qu+1,qu+1+q);
		int pos=1;
		for(int i=1;i<=q;i++){
			while(pos<n && ed[pos].w<=qu[i].y){
				if(dep[ed[pos].u]>dep[ed[pos].v]) swap(ed[pos].u,ed[pos].v);
				update(1,1,n,id[ed[pos].v],ed[pos].w);
				pos++;
			}
			ans[qu[i].index]=querymx(1,qu[i].x);
		}
		for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
	}
	return 0;
}

思路

不可能在线q次重新建树 会tle
我们考虑离线处理 把所有询问记录下来 并把询问和边按照边权从小到大排序
每次只要把比该询问小的权值加入线段树即可 pos维护上一次插入的最后一个位置

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

文章作者:Hippopmonkey

发布时间:2017-09-05, 21:37:55

最后更新:2017-09-06, 16:05:43

原始链接:http://xuboming8.github.io/2017/09/05/树链剖分专题3/

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

文章目录
  1. 1. 树链剖分专题3
    1. 1.1. HDU 5029
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. bzoj 3531
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. HDU 3804
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
|