那天毛主力讲课，讲了可持久化平衡树、可持久化块状链表、可持久化动态树、可持久化动态仙人掌等丧心病狂的数据结构，把蒟蒻虐成了狗。。现在整理一下学过的一些可持久化数据结构

一、可持久化线段树

就是每个新建的点都利用左边、右边已有的节点，用$O(lgn)$建出当前新树

1.静态区间第K大

这个很早以前就学过了，直接可持久化线段树就行了，时空复杂度$O(nlgn)$

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,i,tot,sz,x,y,z,root[100001],ls[8000001],rs[8000001],a[1000001],size[8000001],num[100001],hash[100001]; //root记录根节点位置，l是左孩子，r是右孩子， size表示该节点的总值
void insert(int l,int r,int x,int &y,int k){
	size[y=++sz]=size[x]+1; //新节点的位置和深度
	if(l==r)return;
	ls[y]=ls[x];rs[y]=rs[x]; //若不需更新用从前的路径
	int mid=(l+r)>>1;
	if(a[k]<=hash[mid])insert(l,mid,ls[x],ls[y],k);
				  else insert(mid+1,r,rs[x],rs[y],k);
}
int ask(int l,int r,int x,int y,int k){
	if(l==r)return l;
	int mid=(l+r)>>1; //该区间的左区间上的数比k大，往左区间找
	if(size[ls[y]]-size[ls[x]]>=k)return ask(l,mid,ls[x],ls[y],k); 
	else return ask(mid+1,r,rs[x],rs[y],k-(size[ls[y]]-size[ls[x]]));
}
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++){scanf("%d",&a[i]);num[i]=a[i];}
	sort(num+1,num+n+1);
	hash[++tot]=num[1];
	for(i=2;i<=n;i++)if(num[i]-num[i-1])hash[++tot]=num[i];
	for(i=1;i<=n;i++)insert(1,tot,root[i-1],root[i],i); //逐个节点插入
	for(i=1;i<=m;i++){//逐个询问回复
		scanf("%d%d%d",&x,&y,&z);
		printf("%d\n",hash[ask(1,tot,root[x-1],root[y],z)]);
	}
}

2.动态区间第K大

这个很早以前就会抄过了，大概就是套个树状数组维护线段树前缀和就好啦

#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 2001000
#define M 10100
using namespace std;
int n,m,i,j,cnt,tot,xa,xb,rt,sz,t,T,a[N],L[30],R[30],root[N],ls[N],rs[N],size[N],hash[N],num[N],x[M],y[M],z[M];
char ch[9];bool flag[M];
int lowbit(int x){return x&(-x);}
void insert(int last,int l,int r,int &rt,int w,int z){
	rt=++sz;size[rt]=size[last]+z;
	ls[rt]=ls[last];rs[rt]=rs[last];//继承上一个根 
	if(l==r)return;
	int mid=(l+r)>>1;
	if(w<=hash[mid])insert(ls[last],l,mid,ls[rt],w,z);//插入的节点应在左边 
	else insert(rs[last],mid+1,r,rs[rt],w,z);
}
int query(int l,int r,int w){
	if(l==r)return l;
	int i,mid=(l+r)>>1,suml=0,sumr=0;
	for(i=1;i<=xa;i++)suml+=size[ls[L[i]]];
	for(i=1;i<=xb;i++)sumr+=size[ls[R[i]]];
	if(sumr-suml>=w){//往左找 
		for(i=1;i<=xa;i++)L[i]=ls[L[i]];
		for(i=1;i<=xb;i++)R[i]=ls[R[i]];
		return query(l,mid,w);
	}else{//往右找 
		for(i=1;i<=xa;i++)L[i]=rs[L[i]];
		for(i=1;i<=xb;i++)R[i]=rs[R[i]];
		return query(mid+1,r,w-(sumr-suml));
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++){scanf("%d",&a[i]);num[++cnt]=a[i];}
	for(i=1;i<=m;i++){
		scanf("%s",ch);
		if(ch[0]=='Q'){
			flag[i]=true;
			scanf("%d%d%d",&x[i],&y[i],&z[i]);
		}else{
			scanf("%d%d",&x[i],&y[i]);
			num[++cnt]=y[i];
		}
	}
	sort(num+1,num+cnt+1);
	hash[++tot]=num[1];
	for(i=2;i<=cnt;i++)if(num[i]!=num[i-1])hash[++tot]=num[i];
	for(i=1;i<=n;i++)
		for(j=i;j<=n;j+=lowbit(j))
			insert(root[j],1,tot,root[j],a[i],1);
	for(i=1;i<=m;i++){
		if(flag[i]){
			xa=xb=0;
			for(j=x[i]-1;j;j-=lowbit(j))L[++xa]=root[j];
			for(j=y[i];j;j-=lowbit(j))R[++xb]=root[j];
			printf("%d\n",hash[query(1,tot,z[i])]);
		}else{
			for(j=x[i];j<=n;j+=lowbit(j))
				insert(root[j],1,tot,root[j],a[x[i]],-1);
			a[x[i]]=y[i];
			for(j=x[i];j<=n;j+=lowbit(j))
				insert(root[j],1,tot,root[j],a[x[i]],1);
		}
	}
}

3.树上两点间第K大

很早以前还以为是树链剖分+树套树，但较早以前发现自己too simple，只要利用DFS序，每个点利用他的父亲可持久化，把求前缀和改成求$q(x)+q(y)-q(lca(x,y))-q(fa[lca(x,y)])$就行啦，时空复杂度$O(nlgn)$

#include<cstdio>
#include<algorithm>
#define N 111111
#define M 4444444
using namespace std;
int n,m,i,top,sz,eg,tot,x,y,k,ans,v[N],val[N],hash[N],high[N],last[N<<1],next[N<<1],first[N],id[N],pos[N],root[N],fa[N][18],son[M][2],size[M];
void ins(int x,int y){last[++tot]=y;next[tot]=first[x];first[x]=tot;}
int find(int x){
	int l=1,r=top;
	while(l<r){
		int mid=(l+r)>>1;
		if(hash[mid]<x)l=mid+1;else r=mid;
	}
	return l;
}
void dfs(int x){
	pos[x]=++sz;id[sz]=x;
	for(int i=1;i<=17;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int i=first[x];i;i=next[i]){
		int y=last[i];
		if(y!=fa[x][0]){
			fa[y][0]=x;
			high[y]=high[x]+1;
			dfs(y);
		}
	}
}
void add(int l,int r,int x,int &y,int key){
	y=++eg;size[y]=size[x]+1;
	son[y][0]=son[x][0];son[y][1]=son[x][1];
	if(l==r)return;
	int mid=(l+r)>>1;
	if(key<=mid)add(l,mid,son[x][0],son[y][0],key);
	else add(mid+1,r,son[x][1],son[y][1],key);
}
int lca(int x,int y){
	if(high[x]<high[y])swap(x,y);
	int t=high[x]-high[y];
	for(int i=0;i<=17;i++)if(t&(1<<i))x=fa[x][i];
	for(int i=17;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	if(x==y)return x;return fa[x][0];
}
int query(int a,int b,int k){
	int c=lca(a,b),d=fa[c][0];
	a=root[pos[a]];b=root[pos[b]];c=root[pos[c]];d=root[pos[d]];
	int l=1,r=top;
	while(l<r){
		int mid=(l+r)>>1;
		int tmp=size[son[a][0]]+size[son[b][0]]-size[son[c][0]]-size[son[d][0]];
		if(tmp>=k)r=mid,a=son[a][0],b=son[b][0],c=son[c][0],d=son[d][0];
		else k-=tmp,l=mid+1,a=son[a][1],b=son[b][1],c=son[c][1],d=son[d][1];
	}
	return hash[l];
}
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%d",&val[i]),v[i]=val[i];
	sort(v+1,v+n+1);
	hash[++top]=v[1];
	for(i=2;i<=n;i++)if(v[i]!=v[i-1])hash[++top]=v[i];
	for(i=1;i<=n;i++)val[i]=find(val[i]);
	for(i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	dfs(1);
	for(i=1;i<=n;i++){
		int t=id[i];
		add(1,top,root[pos[fa[t][0]]],root[i],val[t]);
	}
	while(m--){
		scanf("%d%d%d",&x,&y,&k);
		x^=ans;ans=query(x,y,k);
		printf("%d",ans);
		if(m)puts("");
	}
}

4.树上两点间第K大+加边

再加一个启发式合并就可以了，时空复杂度$O(nlg^2n)$

#include<cstdio>
#include<algorithm>
#define N 111111
#define M 12345678
using namespace std;
int T,n,m,i,top,sz,eg,tot,x,y,k,ans,father[N],siz[N],v[N],val[N],hash[N],high[N],last[N<<1],next[N<<1],first[N],id[M],pos[M],root[M],fa[N][17],son[M][2],size[M];
char s[9];void ins(int x,int y){last[++tot]=y;next[tot]=first[x];first[x]=tot;}
int get(int x){
	if(father[x]==x)return father[x];
	return father[x]=get(father[x]);
}
int find(int x){
	int l=1,r=top;
	while(l<r){
		int mid=(l+r)>>1;
		if(hash[mid]<x)l=mid+1;else r=mid;
	}
	return l;
}
void add(int l,int r,int x,int &y,int key){
	y=++eg;size[y]=size[x]+1;
	son[y][0]=son[x][0];son[y][1]=son[x][1];
	if(l==r)return;
	int mid=(l+r)>>1;
	if(key<=mid)add(l,mid,son[x][0],son[y][0],key);
	else add(mid+1,r,son[x][1],son[y][1],key);
}
int lca(int x,int y){
	if(high[x]<high[y])swap(x,y);
	int t=high[x]-high[y];
	for(int i=0;i<=16;i++)if(t&(1<<i))x=fa[x][i];
	for(int i=16;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	if(x==y)return x;return fa[x][0];
}
int query(int a,int b,int k){
	int c=lca(a,b),d=fa[c][0];
	a=root[pos[a]];b=root[pos[b]];c=root[pos[c]];d=root[pos[d]];
	int l=1,r=top;
	while(l<r){
		int mid=(l+r)>>1;
		int tmp=size[son[a][0]]+size[son[b][0]]-size[son[c][0]]-size[son[d][0]];
		if(tmp>=k)r=mid,a=son[a][0],b=son[b][0],c=son[c][0],d=son[d][0];
		else k-=tmp,l=mid+1,a=son[a][1],b=son[b][1],c=son[c][1],d=son[d][1];
	}
	return hash[l];
}
void dfs(int x,int la){
	pos[x]=++sz;id[sz]=x;
	for(int i=1;i<=16;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
	add(1,top,root[pos[fa[x][0]]],root[sz],val[x]);
	for(int i=first[x];i;i=next[i]){
		int y=last[i];
		if(y!=la){
			fa[y][0]=x;
			high[y]=high[x]+1;
			dfs(y,x);
		}
	}
}
void uni(){
	int p=get(x),q=get(y);
	father[p]=q;siz[q]+=siz[p];
	ins(x,y);ins(y,x);
}
int main(){
	scanf("%d",&T);scanf("%d%d%d",&n,&m,&T);
	for(i=1;i<=n;i++)scanf("%d",&val[i]),v[i]=val[i];
	sort(v+1,v+n+1);hash[++top]=v[1];
	for(i=2;i<=n;i++)if(v[i]!=v[i-1])hash[++top]=v[i];
	for(i=1;i<=n;i++)val[i]=find(val[i]);
	for(i=1;i<=n;i++)father[i]=i,siz[i]=1;
	for(i=1;i<=m;i++)scanf("%d%d",&x,&y),uni();
	for(i=1;i<=n;i++)if(!fa[i][0])dfs(i,0);
	while(T--){
		scanf("%s%d%d",s,&x,&y);x^=ans;y^=ans;
		if(s[0]=='Q'){
			scanf("%d",&k);k^=ans;
			printf("%d\n",ans=query(x,y,k));
		}else{
			if(siz[get(x)]>siz[get(y)])swap(x,y);
			uni();fa[x][0]=y;high[x]=high[y]+1;dfs(x,y);
		}
	}
}

BZOJ2653 按值建主席树二分支持在线操作，挺神的

#include<bits/stdc++.h>
#define N 20020
#define M 300300
using namespace std;int n,i,Q,l,r,mid,cnt,tot,ans,T[N],sum[M],lv[M],rv[M],L[M],R[M],q[4];
struct P{int x,y;}p[N];bool cmp(P a,P b){return a.x<b.x;}
void ps(int k){sum[k]=sum[L[k]]+sum[R[k]];lv[k]=max(lv[L[k]],sum[L[k]]+lv[R[k]]);rv[k]=max(rv[R[k]],sum[R[k]]+rv[L[k]]);}
void bt(int l,int r,int&k){
	k=++tot;if(l==r){lv[k]=rv[k]=sum[k]=1;return;}
	int mid=l+r>>1;bt(l,mid,L[k]);bt(mid+1,r,R[k]);ps(k);
}
void cha(int l,int r,int x,int rt,int&k){
	k=++tot;if(l==r){lv[k]=rv[k]=sum[k]=-1;return;}
	int mid=l+r>>1;if(x<=mid)R[k]=R[rt],cha(l,mid,x,L[rt],L[k]);
	else L[k]=L[rt],cha(mid+1,r,x,R[rt],R[k]);ps(k);
}
int qu(int k,int l,int r,int x,int y){
	if(x<=l&&r<=y)return sum[k];int mid=l+r>>1,va=0;if(x<=mid)va+=qu(L[k],l,mid,x,y);
	if(y>mid)va+=qu(R[k],mid+1,r,x,y);return va;
}
int ql(int k,int l,int r,int x,int y){
	if(x<=l&&r<=y)return lv[k];int mid=l+r>>1,va=0;
	if(y<=mid)return ql(L[k],l,mid,x,y);else if(x>mid)return ql(R[k],mid+1,r,x,y);else return max(ql(L[k],l,mid,x,y),qu(L[k],l,mid,x,y)+ql(R[k],mid+1,r,x,y));
}
int qr(int k,int l,int r,int x,int y){
	if(x<=l&&r<=y)return rv[k];int mid=l+r>>1,va=0;
	if(y<=mid)return qr(L[k],l,mid,x,y);else if(x>mid)return qr(R[k],mid+1,r,x,y);else return max(qr(R[k],mid+1,r,x,y),qu(R[k],mid+1,r,x,y)+qr(L[k],l,mid,x,y));
}
bool ok(int k){
	int va=0;if(q[1]+1<q[2])va+=qu(k,0,n-1,q[1]+1,q[2]-1);
	va+=qr(k,0,n-1,q[0],q[1]);va+=ql(k,0,n-1,q[2],q[3]);return va>=0;
}
int main(){
	for(scanf("%d",&n),i=0;i<n;i++)scanf("%d",&p[i].x),p[i].y=i;
	for(sort(p,p+n,cmp),bt(0,n-1,T[0]),i=1;i<n;i++)cha(0,n-1,p[i-1].y,T[i-1],T[i]);
	for(scanf("%d",&Q);Q--;ans=p[ans].x,printf("%d\n",ans)){
		for(i=0;i<4;i++)scanf("%d",&q[i]),q[i]=(q[i]+ans)%n;
		for(sort(q,q+4),l=0,r=n-1;l<=r;)if(ok(T[mid=l+r>>1]))ans=mid,l=mid+1;else r=mid-1;
	}
}

二、可持久化字典树

大概就是和可持久化线段树差不多，大多是处理区间最大异或和的问题，按位贪心再可持久化字典树上判断就行了

BZOJ3261 统计前缀和差分后直接上可持久化字典树就行啦

#include<cstdio>
#define N 12222222
int x,i,n,m,l,r,tot,rt[N],b[N],c[N][2],s[N];char ch[9];
void ins(int x,int &y,int z,int d){
	int p=(z>>d)&1;s[y=++tot]=s[x]+1;if(d<0)return;
	c[y][p^1]=c[x][p^1];ins(c[x][p],c[y][p],z,d-1);
}
int qu(int x,int y,int z,int d){
	if(d<0)return 0;int p=(z>>d)&1;
	if(s[c[y][p^1]]-s[c[x][p^1]])return (1<<d)+qu(c[x][p^1],c[y][p^1],z,d-1);else return qu(c[x][p],c[y][p],z,d-1);
}
int main(){
	for(ins(0,rt[1],0,24),scanf("%d%d",&n,&m),n++,i=2;i<=n;i++)scanf("%d",&x),ins(rt[i-1],rt[i],b[i]=b[i-1]^x,24);
	for(;m--;){
		scanf("%s",ch);
		if(ch[0]=='A')scanf("%d",&x),n++,ins(rt[n-1],rt[n],b[n]=b[n-1]^x,24);
		else scanf("%d%d%d",&l,&r,&x),printf("%d\n",qu(rt[l-1],rt[r],b[n]^x,24));
	}
}

BZOJ3166 统计出左边和右边第一个和第二个比它大的数就变成裸题啦

#include<cstdio>
#include<algorithm>
#define N 50050
using namespace std;
int n,i,h,t,tot,ans,MAX,l[N],ll[N],r[N],rr[N],q[N],rt[N],a[N],s[N*222],c[N*222][2];
int fl(int k){return(a[k]>a[i]||!k)?k:fl(l[k]);}
int fr(int k){return(a[k]>a[i]||k==n+1)?k:fr(r[k]);}
void ins(int x,int &y,int z,int d){
	s[y=++tot]=s[x]+1;if(d<0)return;int p=(z>>d)&1;
	c[y][p^1]=c[x][p^1];ins(c[x][p],c[y][p],z,d-1);
}
int qu(int x,int y,int z,int d){
	if(d<0)return 0;int p=(z>>d)&1;
	if(s[c[y][p^1]]-s[c[x][p^1]])return (1<<d)+qu(c[x][p^1],c[y][p^1],z,d-1);else return qu(c[x][p],c[y][p],z,d-1);
}
int main(){
	for(ins(0,rt[0],0,30),scanf("%d",&n),i=1;i<=n;q[++t]=i++){
		scanf("%d",&a[i]),ins(rt[i-1],rt[i],a[i],30);
		for(;h<t&&a[i]>=a[q[t]];t--);
		l[i]=h>=t?0:q[t];
	}
	for(h=t=0,i=n;i;q[++t]=i--){
		for(;h<t&&a[i]>=a[q[t]];t--);
		r[i]=h>=t?n+1:q[t];
	}
	for(i=2;i<=n;i++)ll[i]=l[i]?fl(l[i]-1):0;
	for(rr[n]=r[n+1]=n+1,i=n-1;i;i--)rr[i]=r[i]<=n?fr(r[i]+1):n+1;
	for(i=1;i<=n;i++){
		if(l[i])ans=max(ans,qu(rt[ll[i]],rt[r[i]-1],a[i],30));
		if(r[i]<=n)ans=max(ans,qu(rt[l[i]],rt[rr[i]-1],a[i],30));
	}
	printf("%d",ans);
}

BZOJ2741 分块+可持久化Tire 复杂度$O(n\sqrt{n}lgn)$

#include<bits/stdc++.h>
#define N 12222
#define M 666666
using namespace std;
int n,m,i,j,w,x,y,sx,bx,by,S=150,nb,zs,ans,a[N],T[N],bl[N],f[99][N],ed[99],sz[M],c[M][2];
void ins(int x,int&y,int z,int d){
	int p=z>>d&1;sz[y=++nb]=sz[x]+1;if(d<0)return;
	c[y][p^1]=c[x][p^1];ins(c[x][p],c[y][p],z,d-1);
}
int qu(int x,int y,int z,int d){
    if(d<0)return 0;int p=(z>>d)&1;
    if(sz[c[y][p^1]]-sz[c[x][p^1]])return (1<<d)+qu(c[x][p^1],c[y][p^1],z,d-1);else return qu(c[x][p],c[y][p],z,d-1);
}int main(){
	for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d",&a[i]),a[i]^=a[i-1],ins(T[i-1],T[i],a[i],30),bl[i]=(i-1)/S,ed[zs=bl[i]]=i;
	for(i=1;i<=zs;i++)for(j=ed[i-1]+1;j<=n;j++)f[i][j]=max(f[i][j-1],qu(T[ed[i-1]],T[j],a[j],30));
	for(;m--;printf("%d\n",ans)){
		scanf("%d%d",&x,&y);x=(int)(((long long)x+ans)%n)+1;y=(int)(((long long)y+ans)%n)+1;if(x>y)swap(x,y);bx=bl[x];by=bl[y];sx=ed[bl[x]]+1;ans=sx>y?0:f[bx+1][y];
		for(i=x;i<=min(sx,y);i++)ans=max(ans,qu(T[i-1],T[y],a[i-1],30));
	}
}

三、可持久化平衡树

先把黄主力的模板复过来再说。。

#include<bits/stdc++.h>
#define N 400010
using namespace std;
int head[N],ne[N],v[N],n,i,fa[N],m,V[N],t,ux,uy,tx,ty,sx,sy;
long long sum[N],cov[N],ans,key;
int ls[N],rs[N],sz[N],dad[N],np,ran[N],root,l,x,y;
void add(int x,int y){v[++l]=y;ne[l]=head[x];head[x]=l;}
int nn(int x,int y){ran[y]=rand();sum[y]=V[y]=x;ls[y]=rs[y]=cov[y]=dad[y]=0;sz[y]=1;}
void ps(int x){
    sum[x]=sum[ls[x]]+sum[rs[x]]+V[x];
    sz[x]=sz[ls[x]]+sz[rs[x]]+1;
    dad[ls[x]]=x;dad[rs[x]]=x;//这里维护father信息才能进行一系列BST操作 
}
void pd(int x){
    if(ls[x])V[ls[x]]+=cov[x],cov[ls[x]]+=cov[x],sum[ls[x]]+=sz[ls[x]]*cov[x];
    if(rs[x])V[rs[x]]+=cov[x],cov[rs[x]]+=cov[x],sum[rs[x]]+=sz[rs[x]]*cov[x];
    cov[x]=0;
}
int merge(int x,int y){//merge操作，合并两个无∪平衡树 
    if(!x||!y)return x?x:y;int z=0;
    if(ran[x]>ran[y])pd(y),z=y,ls[z]=merge(x,ls[y]);else pd(x),z=x,rs[z]=merge(rs[x],y);
    ps(z);return z;
}
void split(int x,int &y,int &z,int k){//分离操作，在k大小处分离，返回两颗子树根 
    y=z=0;if(!x)return;pd(x);
    if(sz[ls[x]]>=k)z=x,split(ls[x],y,ls[z],k),ps(z);
    else y=x,split(rs[x],rs[y],z,k-sz[ls[x]]-1),ps(y);
}
void dfs(int x){//对初始的树进行DFS 
    root=merge(root,x);
    for(int i=head[x];i;i=ne[i])if(v[i]!=fa[x])fa[v[i]]=x,dfs(v[i]);
    root=merge(root,x+np);
}
int find(int x){//找到x的位置 
    int ans=sz[ls[x]]+1,u;
    for(;dad[x];x=u){
        u=dad[x];
        if(x==rs[u])ans+=sz[ls[u]]+1;
    }
    return ans;
}
long long query(int x,int l,int r){//区间询问 
    pd(x);
    if(l<=1&&r>=sz[x])return sum[x];
    long long ans=0;
    if(l<=sz[ls[x]]+1&&r>sz[ls[x]])ans=V[x];
    if(l<=sz[ls[x]])ans+=query(ls[x],l,r);
    if(r>sz[ls[x]]+1)ans+=query(rs[x],l-sz[ls[x]]-1,r-sz[ls[x]]-1);
    ps(x);return ans;
}
void add(int x,int l,int r,long long k){//区间修改 
    pd(x);
    if(l<=1&&r>=sz[x]){sum[x]+=sz[x]*k,cov[x]+=k,V[x]+=k;return;}
    if(l<=sz[ls[x]]+1&&r>sz[ls[x]])V[x]+=k;
    if(l<=sz[ls[x]])add(ls[x],l,r,k);
    if(r>sz[ls[x]]+1)add(rs[x],l-sz[ls[x]]-1,r-sz[ls[x]]-1,k);
    ps(x);
} 
int main(){
    srand(23333);scanf("%d",&n);np=200000;
    for(i=1;i<=n;i++)scanf("%d",&x),nn(x,i),nn(x,i+np);
    for(i=1;i<n;i++)scanf("%d%d",&x,&y),x++,y++,add(x,y),add(y,x);
    dfs(1);scanf("%d",&m);
    while(m--){
        scanf("%d%lld",&t,&key);x=key+ans+1;
        if(t==1){//加新点，先把这颗子树拆下来按顺序合并 
            scanf("%d",&y);
            nn(y,++n);nn(y,n+np);
            split(root,ux,uy,find(x));
            root=merge(ux,merge(n,merge(n+np,uy)));
        }
        if(t==2){//括号序列区间修改 
            scanf("%d",&y);
            add(root,find(x),find(x+np),y);
        }
        if(t==3){//删除一个子树，就是把这个子树括号序列中两个位置拆下来 
            ux=find(x);uy=find(x+np);
            split(root,tx,ty,uy);
            split(tx,sx,sy,ux-1);
            root=merge(sx,ty);
        }
        if(t==4)printf("%lld\n",ans=query(root,find(x),find(x+np))>>1);//因为每个点出现了两次，故答案/2 
    }
}

BZOJ2658 非常神的题，一行一行扫下来，维护一颗深度逐渐增加的二叉树，如果碰到障碍就把该点深度改为0，每个点对答案的贡献是∑(h[x]-h[fa])*sz[x]*(sz[x]+1)/2，考虑用数据结构维护

因为数据是随机的，可以用可持久化Treap，非常方便，每次把要改的点取下来改就可以了

#include<bits/stdc++.h>
#define N 44444
using namespace std;long long ans,S[N];
int n,m,i,j,k,rt,u1,u2,u3,u4,v[N],la[N],L[N],R[N],sz[N];
struct P{int x,y;}p[111111];bool cmp(P a,P b){return a.x<b.x;}
void up(int k,int z){if(!k)return;la[k]+=z;v[k]+=z;}
void pd(int k){if(la[k])up(L[k],la[k]),up(R[k],la[k]),la[k]=0;}
void ps(int k){
	int l=L[k],r=R[k];sz[k]=sz[l]+sz[r]+1;
	S[k]=S[l]+S[r]+1ll*(v[l]-v[k])*sz[l]*(sz[l]+1)/2+1ll*(v[r]-v[k])*sz[r]*(sz[r]+1)/2;
}
int mg(int x,int y){
	if(!y)return ps(x),x;if(!x)return ps(y),y;pd(x);pd(y);
	if(v[x]<v[y])return R[x]=mg(R[x],y),ps(x),x;else return L[y]=mg(x,L[y]),ps(y),y;
}
void sl(int x,int&y,int&z,int k){
	y=z=0;if(!x)return;pd(x);
	if(sz[L[x]]>=k)z=x,sl(L[x],y,L[z],k),ps(z);else y=x,sl(R[x],R[y],z,k-sz[L[x]]-1),ps(y);
}
int main(){
	for(scanf("%d%d%d",&n,&m,&k),i=1;i<=k;i++)scanf("%d%d",&p[i].x,&p[i].y);
	for(sort(p+1,p+k+1,cmp),i=1;i<=m;i++)rt=mg(rt,i);
	for(ans=1ll*n*(n+1)*m*(m+1)/4,i=j=1;i<=n;ans-=S[rt]+1ll*v[rt]*m*(m+1)/2,i++)
		for(up(rt,1);p[j].x==i;j++)sl(rt,u1,u2,p[j].y-1),sl(u2,u3,u4,1),v[u3]=0,rt=mg(mg(u1,u3),u4);
	printf("%lld",ans);
}

四、可持久化块状链表：我这种蒟蒻连块状链表都不太会呢，让我写这个。。

• 相关文章推荐
• 全局相关文章