可持久化数据结构

orz hhw posted @ 2015年10月05日 13:00 in 算法学习 with tags 数据结构 模板 bzoj 主席树 算法学习 可持久化 , 8981 阅读

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

一、可持久化线段树

就是每个新建的点都利用左边、右边已有的节点,用$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);
}

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

 

Avatar_small
NCERT Science Sample 说:
2022年9月28日 13:12

Science is very close to our world, which means everything in this world has a relation with science. NCERT Science Sample Paper Class 2 From living things such as humans, plants and animals etc. to Non-living things such as rocks, elements and so on must depend on the science. Simply without science, there is nothing. Hence this subject has been introduced in primary education in the country.Follow NCERT Science Model Papers 2023 Class 2 do favour to every 2nd standard student to get top score in all formats of exams conducted in Term-1, Term-2 for Summative Assessments.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter