差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:树链剖分_lgwza [2020/08/04 22:20]
lgwza
+++ 2020-2021:teams:legal_string:树链剖分_lgwza [2020/08/04 22:21] (当前版本)
lgwza [例题]
@@ 行 182: / 行 182: @@
 ===== 例题 =====
 [[https://www.luogu.com.cn/problem/P3384|P3384 【模板】轻重链剖分]]
+参考代码：
+<hidden>
+<code cpp>
+#include<bits/stdc++.h>
+using namespace std;
+const int N=1e5+5;
+typedef long long ll;
+int n,m,root,mod;
+int cnt,head[N],nxt[N<<1],to[N<<1],w[N],nw[N];
+int tr[N<<2],add[N<<2];
+int hson[N],dfn[N],fa[N],tot,dep[N],siz[N],top[N],rk[N];
+void addedge(int u,int v){
+	nxt[++cnt]=head[u];
+	head[u]=cnt;
+	to[cnt]=v;
+}
+// segment tree
+inline int ls(int o){
+	return o<<1;
+}
+inline int rs(int o){
+	return o<<1|1;
+}
+void push_up(int o){
+	tr[o]=(tr[ls(o)]+tr[rs(o)])%mod;
+}
+void build(int o,int l,int r){
+	if(l==r){
+		tr[o]=nw[l]%mod;
+		return;
+	}
+	int mid=l+r>>1;
+	build(ls(o),l,mid);
+	build(rs(o),mid+1,r);
+	push_up(o);
+}
+void f(int o,int l,int r,int k){
+	add[o]=(add[o]+k);
+	tr[o]=(tr[o]+(r-l+1)*k)%mod;
+}
+void push_down(int o,int l,int r){
+	int mid=l+r>>1;
+	f(ls(o),l,mid,add[o]);
+	f(rs(o),mid+1,r,add[o]);
+	add[o]=0;
+}
+void xg(int o,int nl,int nr,int l,int r,int k){
+	if(nl<=l&&r<=nr){
+		add[o]=(add[o]+k)%mod;
+		tr[o]=(tr[o]+(r-l+1)*k)%mod;
+		return;
+	}
+	push_down(o,l,r);
+	int mid=l+r>>1;
+	if(nl<=mid) xg(ls(o),nl,nr,l,mid,k);
+	if(nr>mid) xg(rs(o),nl,nr,mid+1,r,k);
+	push_up(o);
+}
+int cx(int o,int nl,int nr,int l,int r){
+	if(nl<=l&&r<=nr) return tr[o]%mod;
+	push_down(o,l,r);
+	int ret=0;
+	int mid=l+r>>1;
+	if(nl<=mid) ret+=cx(ls(o),nl,nr,l,mid);
+	if(nr>mid) ret+=cx(rs(o),nl,nr,mid+1,r);
+	return ret%mod;
+}
+// original tree
+int cxRange(int x,int y){
+	int ans=0;
+	while(top[x]!=top[y]){
+		if(dep[top[x]]<dep[top[y]]) swap(x,y);
+		ans+=cx(1,dfn[top[x]],dfn[x],1,n);
+		ans%=mod;
+		x=fa[top[x]];
+	}
+	if(dep[x]>dep[y]) swap(x,y);
+	ans+=cx(1,dfn[x],dfn[y],1,n);
+	ans%=mod;
+	return ans;
+}
+void xgRange(int x,int y,int k){
+	k%=mod;
+	while(top[x]!=top[y]){
+		if(dep[top[x]]<dep[top[y]]) swap(x,y);
+		xg(1,dfn[top[x]],dfn[x],1,n,k);
+		x=fa[top[x]];
+	}
+	if(dep[x]>dep[y]) swap(x,y);
+	xg(1,dfn[x],dfn[y],1,n,k);
+}
+int cxSon(int x){
+	return cx(1,dfn[x],dfn[x]+siz[x]-1,1,n);
+}
+void xgSon(int x,int k){
+	xg(1,dfn[x],dfn[x]+siz[x]-1,1,n,k);
+}
+// dfs
+void dfs1(int u,int f,int deep){
+	dep[u]=deep;
+	siz[u]=1;
+	fa[u]=f;
+	for(int i=head[u];i;i=nxt[i]){
+		int v=to[i];
+		if(v==fa[u]) continue;
+		dfs1(v,u,deep+1);
+		siz[u]+=siz[v];
+		if(hson[u]==0||siz[hson[u]]<siz[v]) hson[u]=v;
+	}
+}
+void dfs2(int u,int t){
+	top[u]=t;
+	dfn[u]=++tot;
+	nw[tot]=w[u];
+	rk[tot]=u;
+	if(!hson[u]) return;
+	dfs2(hson[u],t);
+	for(int i=head[u];i;i=nxt[i]){
+		int v=to[i];
+		if(v==fa[u]||v==hson[u]) continue;
+		dfs2(v,v);
+	}
+}
+int main(){
+	scanf("%d %d %d %d",&n,&m,&root,&mod);
+	for(int i=1;i<=n;i++) scanf("%d",&w[i]);
+	for(int i=1;i<=n-1;i++){
+		int x,y;
+		scanf("%d %d",&x,&y);
+		addedge(x,y);
+		addedge(y,x);
+	}
+	dfs1(root,0,1);
+	dfs2(root,root);
+	build(1,1,n);
+//	printf("fadfa\n");
+	while(m--){
+		int op;
+		scanf("%d",&op);
+		if(op==1){
+			int x,y;
+			int k;
+			scanf("%d %d %d",&x,&y,&k);
+			k%=mod;
+			xgRange(x,y,k);
+		}
+		else if(op==2){
+			int x,y;
+			scanf("%d %d",&x,&y);
+			printf("%d\n",cxRange(x,y));
+		}
+		else if(op==3){
+			int x;
+			int k;
+			scanf("%d %d",&x,&k);
+			k%=mod;
+			xgSon(x,k);
+		}
+		else if(op==4){
+			int x;
+			scanf("%d",&x);
+			printf("%d\n",cxSon(x));
+		}
+	}
+	return 0;
+}
+</code>
+</hidden>
 ===== 参考资料 =====
 [[https://oi-wiki.org/graph/hld/|OI Wiki]]

CVBB ACM Team

用户工具

站点工具

差别

页面工具