CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:重链剖分 [2020/05/24 18:01]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:重链剖分 [2021/08/04 20:37] (当前版本)
jxm2001 [代码模板]
@@ 行 5: / 行 5: @@
 一种动态维护树上路径、子树信息的算法，单次操作时间复杂度 $O\left(\log^2 n\right)$
-===== 算法思想 ====
+===== 算法思想 =====
 重链剖分的关键是把树上修改问题转化为区间修改问题
@@ 行 44: / 行 44: @@
 题目大意是说给定一棵 $n$ 个结点的点权树，每次操作为查询路径或子树上的权值和，或者给路径或子树上的每个点权值加 $v$ ，所有结果取模
-代码
 <hidden 查看代码>
 <code cpp>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <cctype>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=1e5+5;
 int mod;
@@ 行 146: / 行 115: @@
 	head[u]=m;
 }
-int d[MAXN],w[MAXN],sz[MAXN],f[MAXN],dfs_id[MAXN],dfs_t;
+int d[MAXN],w[MAXN],sz[MAXN],f[MAXN],dfn[MAXN],dfs_t;
-int h_son[MAXN],mson[MAXN],p[MAXN],dfs_w[MAXN];
+int h_son[MAXN],mson[MAXN],p[MAXN],dfw[MAXN];
 void dfs_1(int u,int fa,int depth){
-	sz[u]=1;f[u]=fa;d[u]=depth;mson[u]=0;
+	sz[u]=1,f[u]=fa,d[u]=depth,mson[u]=0;
 	for(int i=head[u];i;i=edge[i].next){
 		int v=edge[i].to;
@@ 行 163: / 行 132: @@
 }
 void dfs_2(int u,int top){
-	dfs_id[u]=++dfs_t;p[u]=top;dfs_w[dfs_t]=w[u];
+	dfn[u]=++dfs_t,p[u]=top;
+	dfw[dfs_t]=w[u];
 	if(mson[u])
 	dfs_2(h_son[u],top);
@@ 行 173: / 行 143: @@
 	}
 }
-LL query_son(int u){return tree.query(1,dfs_id[u],dfs_id[u]+sz[u]-1);}
+int query_path(int u,int v){
-void update_son(int u,int w){tree.update(1,dfs_id[u],dfs_id[u]+sz[u]-1,w);}
-LL query_path(int u,int v){
 	LL ans=0;
 	while(p[u]!=p[v]){
 		if(d[p[u]]<d[p[v]])
 		swap(u,v);
-		ans=(ans+tree.query(1,dfs_id[p[u]],dfs_id[u]))%mod;
+		ans=(ans+tree.query(1,dfn[p[u]],dfn[u]))%mod;
 		u=f[p[u]];
 	}
 	if(d[u]>d[v])
 	swap(u,v);
-	ans=(ans+tree.query(1,dfs_id[u],dfs_id[v]))%mod;
+	ans=(ans+tree.query(1,dfn[u],dfn[v]))%mod;
 	return ans;
 }
@@ 行 192: / 行 160: @@
 		if(d[p[u]]<d[p[v]])
 		swap(u,v);
-		tree.update(1,dfs_id[p[u]],dfs_id[u],w);
+		tree.update(1,dfn[p[u]],dfn[u],w);
 		u=f[p[u]];
 	}
 	if(d[u]>d[v])
 	swap(u,v);
-	tree.update(1,dfs_id[u],dfs_id[v],w);
+	tree.update(1,dfn[u],dfn[v],w);
 }
+int query_son(int u){return tree.query(1,dfn[u],dfn[u]+sz[u]-1);}
+void update_son(int u,int w){tree.update(1,dfn[u],dfn[u]+sz[u]-1,w);}
 int main()
 {
@@ 行 246: / 行 216: @@
 而路径修改/查询注意跳过 $\text{LCA}$ 即可
-代码
 <hidden 查看代码>
 <code cpp>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <cctype>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=1e5+5;
 #define lowbit(x) ((x)&(-x))
@@ 行 405: / 行 345: @@
 .询问节点 $a$ 到节点 $b$ 的路径上的颜色段数量(颜色段的定义是极长的连续相同颜色被认为是一段)
+一道很好的重链剖分练手题，这里仅给出代码
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5;
+int lef_color,rig_color;
+struct Tree{
+	int a[MAXN<<2],lazy[MAXN<<2],lc[MAXN<<2],rc[MAXN<<2],sum[MAXN<<2];
+	int lef[MAXN<<2],rig[MAXN<<2];
+	void init(int n,int *w){
+		_rep(i,1,n)
+		a[i]=w[i];
+		build(1,1,n);
+	}
+	void push_up(int k){
+		sum[k]=sum[k<<1]+sum[k<<1|1];
+		lc[k]=lc[k<<1];
+		rc[k]=rc[k<<1|1];
+		if(rc[k<<1]==lc[k<<1|1])
+		sum[k]--;
+	}
+	void build(int k,int L,int R){
+		lef[k]=L,rig[k]=R;
+		int M=L+R>>1;
+		if(L==R){
+			sum[k]=1;
+			lc[k]=rc[k]=a[M];
+			return;
+		}
+		build(k<<1,L,M);
+		build(k<<1|1,M+1,R);
+		push_up(k);
+	}
+	void push_lazy(int k,int lz){
+		lazy[k]=lc[k]=rc[k]=lz;
+		sum[k]=1;
+	}
+	void push_down(int k){
+		if(lazy[k]){
+			push_lazy(k<<1,lazy[k]);
+			push_lazy(k<<1|1,lazy[k]);
+			lazy[k]=0;
+		}
+	}
+	int query(int k,int L,int R){
+		if(L<=lef[k]&&rig[k]<=R){
+			if(lef[k]==L)
+			lef_color=lc[k];
+			if(rig[k]==R)
+			rig_color=rc[k];
+			return sum[k];
+		}
+		push_down(k);
+		int mid=lef[k]+rig[k]>>1;
+		if(mid>=R)
+		return query(k<<1,L,R);
+		else if(mid<L)
+		return query(k<<1|1,L,R);
+		else{
+			if(rc[k<<1]==lc[k<<1|1])
+			return query(k<<1,L,R)+query(k<<1|1,L,R)-1;
+			else
+			return query(k<<1,L,R)+query(k<<1|1,L,R);
+		}
+	}
+	void update(int k,int L,int R,int c){
+		if(L<=lef[k]&&rig[k]<=R){
+			push_lazy(k,c);
+			return;
+		}
+		push_down(k);
+		int mid=lef[k]+rig[k]>>1;
+		if(mid>=L)
+		update(k<<1,L,R,c);
+		if(mid<R)
+		update(k<<1|1,L,R,c);
+		push_up(k);
+	}
+}tree;
+struct Edge{
+	int to,next;
+}edge[MAXN<<1];
+int head[MAXN],m;
+void Insert(int u,int v){
+	edge[++m].to=v;
+	edge[m].next=head[u];
+	head[u]=m;
+}
+int d[MAXN],w[MAXN],sz[MAXN],f[MAXN],dfs_id[MAXN],dfs_t;
+int h_son[MAXN],mson[MAXN],p[MAXN],dfs_w[MAXN];
+void dfs_1(int u,int fa,int depth){
+	sz[u]=1;f[u]=fa;d[u]=depth;mson[u]=0;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)
+		continue;
+		dfs_1(v,u,depth+1);
+		sz[u]+=sz[v];
+		if(sz[v]>mson[u]){
+			h_son[u]=v;
+			mson[u]=sz[v];
+		}
+	}
+}
+void dfs_2(int u,int top){
+	dfs_id[u]=++dfs_t;p[u]=top;dfs_w[dfs_t]=w[u];
+	if(mson[u])
+	dfs_2(h_son[u],top);
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==f[u]||v==h_son[u])
+		continue;
+		dfs_2(v,v);
+	}
+}
+int query_path(int u,int v){
+	int c1=-1,c2=-1,ans=0;
+	while(p[u]!=p[v]){
+		if(d[p[u]]<d[p[v]]){
+			swap(u,v);
+			swap(c1,c2);
+		}
+		ans+=tree.query(1,dfs_id[p[u]],dfs_id[u]);
+		if(c1==rig_color)
+		ans--;
+		c1=lef_color;
+		u=f[p[u]];
+	}
+	if(d[u]>d[v]){
+		swap(u,v);
+		swap(c1,c2);
+	}
+	ans+=tree.query(1,dfs_id[u],dfs_id[v]);
+	if(c1==lef_color)
+	ans--;
+	if(rig_color==c2)
+	ans--;
+	return ans;
+}
+void update_path(int u,int v,int w){
+	while(p[u]!=p[v]){
+		if(d[p[u]]<d[p[v]])
+		swap(u,v);
+		tree.update(1,dfs_id[p[u]],dfs_id[u],w);
+		u=f[p[u]];
+	}
+	if(d[u]>d[v])
+	swap(u,v);
+	tree.update(1,dfs_id[u],dfs_id[v],w);
+}
+int main()
+{
+	int n=read_int(),q=read_int(),root=1,x,y;
+	char opt;
+	_rep(i,1,n)
+	w[i]=read_int();
+	_for(i,1,n){
+		x=read_int(),y=read_int();
+		Insert(x,y);
+		Insert(y,x);
+	}
+	dfs_1(root,-1,0);
+	dfs_2(root,root);
+	tree.init(n,dfs_w);
+	while(q--){
+		opt=get_char();
+		x=read_int();y=read_int();
+		if(opt=='C')
+		update_path(x,y,read_int());
+		else
+		enter(query_path(x,y));
+	}
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

页面工具