可持久化数据结构学习笔记
1. 可持久化线段树(主席树)
主席树求解的问题一般是区间历史求值的问题，即对一些点进行操作后，求其中一个版本的答案
最朴素的方法就是每一次操作都将原线段树复制一遍，但是这样很费空间，而且产生了大量无用的点
但是可以发现，每次修改时所走的路径其实只经过了根到对应叶子的 \(logn\) 个点，所以是否可以只对这些点建新树
大概就是这么个东西，可以发现，在这种情况下，每次修改只需要加入新的链就可以了
此时，每个节点不一定只有一个父亲，但是每个父亲至多有 2 个儿子，而且将每个根拎出来，都是一颗完整的线段树
所以只需要知道每个版本的根就能求解了
对于建树和储存，可以动态开点，根另开数组储存即可
例题：
【模板】可持久化线段树 1
直接维护权值即可，注意复制的数组就是查询的数组
点击查看代码
#include<cstdio>
using namespace std;
const int N=1e6+5;
int n,m,a[N],ls[N*30],rs[N*30],val[N*30],tot,rt[N],cnt;
int build(int p,int l,int r)
{
p=++tot;
if(l==r)
{
val[p]=a[l];
return p;
}
int mid=(l+r)>>1;
ls[p]=build(ls[p],l,mid);
rs[p]=build(rs[p],mid+1,r);
return p;
}
int update(int id,int l,int r,int x,int v)
{
int p=++tot;
if(l==r)
{
val[p]=v;
return p;
}
int mid=(l+r)>>1;
if(x<=mid) ls[p]=update(ls[id],l,mid,x,v),rs[p]=rs[id];
else rs[p]=update(rs[id],mid+1,r,x,v),ls[p]=ls[id];
return p;
}
int query(int p,int l,int r,int x)
{
// printf("%d %d %d %d\n",p,l,r,x);
if(l==r)
{
return val[p];
}
int mid=(l+r)>>1;
if(x<=mid) return query(ls[p],l,mid,x);
else return query(rs[p],mid+1,r,x);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
rt[0]=build(rt[0],1,n);
while(m--)
{
int id,opt,x,y;
scanf("%d%d%d",&id,&opt,&x);
if(opt==1)
{
scanf("%d",&y);
rt[++cnt]=update(rt[id],1,n,x,y);
// printf("%d %d %d\n",rt[cnt],ls[rt[cnt]],val[tot]);
}
else
{
cnt++;
rt[cnt]=rt[id];
printf("%d\n",query(rt[id],1,n,x));
}
}
return 0;
}
【模板】可持久化线段树 2
https://www.gxyzoj.com/d/gxyznoi/p/1
是经典题，涉及值域，先离散化
因为小于等于每个值的数量是单调的，所以可以差分
先考虑区间 \([1,x]\) 怎么做，显然，当 \(x=n\) 时，直接在线段树上二分就行了
但是如果不是 \(n\) 时，就要将多余的部分删掉，因为是按顺序的，可以将下标作为时间，然后主席树处理即可
点击查看代码
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e5+5;
int n,a[N],b[N],ls[N*30],rs[N*30],val[N*30],tot,q,rt[N];
int build(int p,int l,int r)
{
p=++tot;
if(l==r) return p;
int mid=(l+r)>>1;
ls[p]=build(ls[p],l,mid);
rs[p]=build(rs[p],mid+1,r);
return p;
}
int update(int id,int l,int r,int x)
{
int p=++tot;
if(l==r)
{
val[p]=1+val[id];
return p;
}
int mid=(l+r)>>1;
if(x<=mid) ls[p]=update(ls[id],l,mid,x),rs[p]=rs[id];
else rs[p]=update(rs[id],mid+1,r,x),ls[p]=ls[id];
val[p]=val[ls[p]]+val[rs[p]];
return p;
}
int query(int x,int y,int l,int r,int k)
{
if(l==r)
{
return l;
}
int mid=(l+r)>>1;
if(val[ls[x]]-val[ls[y]]>=k) return query(ls[x],ls[y],l,mid,k);
else return query(rs[x],rs[y],mid+1,r,k-val[ls[x]]+val[ls[y]]);
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(b+1,b+n+1);
rt[0]=build(0,1,n);
for(int i=1;i<=n;i++)
{
a[i]=lower_bound(b+1,b+n+1,a[i])-b;
rt[i]=update(rt[i-1],1,n,a[i]);
}
while(q--)
{
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",b[query(rt[r],rt[l-1],1,n,k)]);
}
return 0;
}
P3722 [AH2017/HNOI2017] 影魔
https://www.gxyzoj.com/d/gxyznoi/p/P6
四种情况，记 \(l_i\) 为前面第一个比它大的数的位置，\(r_i\) 是后面
-
\([l_i,r_i]\) 贡献为 \(p1\)
-
\([i,i+1]\) 贡献为 \(p1\)
-
\([l_i,(i+1,r_i-1)]\) 贡献为 \(p2\)
-
\([(l_i+1,i-1),r_i]\) 贡献为 \(p2\)
在更新时就涉及区间修改，但不能下放标记，考虑标记永久化
这个东西就是累加经过的标记，再在末端和数量统一相乘
点击查看代码
#include<cstdio>
#define ll long long
using namespace std;
const int N=2e5+5;
int n,m,a[N],top,s[N],l[N],r[N],rt[N],tot;
ll p1,p2,ls[N*32],rs[N*32],val[N*32],tag[N*32];
int build(int p,int l,int r)
{
p=++tot;
if(l==r) return p;
int mid=(l+r)>>1;
ls[p]=build(0,l,mid);
rs[p]=build(0,mid+1,r);
return p;
}
int update(int p,int l,int r,int ql,int qr,ll x)
{
if(!p) p=++tot;
// printf("%d %d %d %d %d\n",p,l,r,ql,qr);
val[p]+=1ll*(qr-ql+1)*x;
if(ql==l&&qr==r)
{
tag[p]+=x;
return p;
}
int mid=(l+r)>>1;
if(qr<=mid) ls[p]=update(ls[p],l,mid,ql,qr,x);
else if(ql>mid) rs[p]=update(rs[p],mid+1,r,ql,qr,x);
else ls[p]=update(ls[p],l,mid,ql,mid,x),
rs[p]=update(rs[p],mid+1,r,mid+1,qr,x);
return p;
}
int merge(int x,int y)
{
if(!x||!y) return x+y;
val[x]+=val[y],tag[x]+=tag[y];
ls[x]=merge(ls[x],ls[y]);
rs[x]=merge(rs[x],rs[y]);
return x;
}
ll query(int p,int l,int r,int ql,int qr,ll ad)
{
if(l==ql&&r==qr)
{
return val[p]+1ll*(r-l+1)*ad;
}
int mid=(l+r)>>1;
if(qr<=mid) return query(ls[p],l,mid,ql,qr,ad+tag[p]);
else if(ql>mid) return query(rs[p],mid+1,r,ql,qr,ad+tag[p]);
else return query(ls[p],l,mid,ql,mid,ad+tag[p])+
query(rs[p],mid+1,r,mid+1,qr,ad+tag[p]);
}
int main()
{
scanf("%d%d%lld%lld",&n,&m,&p1,&p2);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++)
{
while(top&&a[s[top]]<=a[i]) top--;
l[i]=s[top];
s[++top]=i;
}
s[0]=n+1,top=0;
for(int i=n;i>0;i--)
{
while(top&&a[s[top]]<=a[i]) top--;
r[i]=s[top];
s[++top]=i;
}
rt[0]=build(0,1,n);
// printf("%d ",tot);
for(int i=1;i<=n;i++)
{
if(i!=n) rt[i]=update(rt[i],1,n,i+1,i+1,p1);
// printf("%d %d\n",l[i],r[i]);
if(l[i]&&r[i]!=n+1) rt[r[i]]=update(rt[r[i]],1,n,l[i],l[i],p1);
if(l[i]&&i+2<=r[i]) rt[l[i]]=update(rt[l[i]],1,n,i+1,r[i]-1,p2);
if(r[i]!=n+1&&i-2>=l[i]) rt[r[i]]=update(rt[r[i]],1,n,l[i]+1,i-1,p2);
}
for(int i=1;i<=n;i++)
{
rt[i]=merge(rt[i],rt[i-1]);
}
while(m--)
{
int l,r;
scanf("%d%d",&l,&r);
printf("%lld\n",query(rt[r],1,n,l,r,0)-query(rt[l-1],1,n,l,r,0));
}
return 0;
}
[国家集训队] middle
https://www.gxyzoj.com/d/gxyznoi/p/P8
可以二分中位数，此时将大于等于 mid 的数记为 1，其余记为 -1，那么如果有区间和为正数，就满足
所以就涉及一个区间求和，和最大前/后缀和
因为涉及值的问题，可以以值的大小作为根的编号，提前建好可持久化线段树
至于树上的合并，因为和山海经一样比较复杂，可以用结构体
点击查看代码
#include<cstdio>
#include<algorithm>
#define lid tr[p].ls
#define rid tr[p].rs
using namespace std;
const int N=20005,M=5e6;
int n,v[N],id[N],m,rt[N],tot,q;
bool cmp(int x,int y)
{
return v[x]<v[y];
}
struct tree{
int lmax,rmax,sum,ls,rs;
}tr[M];
int build(int p,int l,int r)
{
p=++tot;
tr[p].lmax=tr[p].rmax=tr[p].sum=r-l+1;
if(l==r) return p;
int mid=(l+r)>>1;
lid=build(0,l,mid);
rid=build(0,mid+1,r);
return p;
}
tree pushup(tree x,tree y,int ls,int rs)
{
tree tmp;
tmp.ls=ls,tmp.rs=rs,tmp.sum=x.sum+y.sum;
tmp.lmax=max(x.lmax,x.sum+y.lmax);
tmp.rmax=max(y.rmax,y.sum+x.rmax);
return tmp;
}
int update(int p,int l,int r,int x)
{
tr[++tot]=tr[p];
p=tot;
if(l==r)
{
tr[p].lmax=tr[p].rmax=tr[p].sum=-1;
return p;
}
int mid=(l+r)>>1;
if(x<=mid) lid=update(lid,l,mid,x);
else rid=update(rid,mid+1,r,x);
tr[p]=pushup(tr[lid],tr[rid],lid,rid);
return p;
}
tree query(int p,int l,int r,int ql,int qr)
{
if(ql>qr) return tr[0];
if(l==ql&&r==qr)
{
return tr[p];
}
int mid=(l+r)>>1;
if(qr<=mid) return query(lid,l,mid,ql,qr);
else if(ql>mid) return query(rid,mid+1,r,ql,qr);
else return pushup(query(lid,l,mid,ql,mid),query(rid,mid+1,r,mid+1,qr),0,0);
}
bool check(int x,int a,int b,int c,int d)
{
tree t1=query(rt[x],1,n,b+1,c-1);
tree t2=query(rt[x],1,n,a,b);
tree t3=query(rt[x],1,n,c,d);
if(t1.sum+t2.rmax+t3.lmax>=0) return 1;
return 0;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&v[i]);
id[i]=i;
}
sort(id+1,id+n+1,cmp);
rt[1]=build(0,1,n);
for(int i=2;i<=n;i++)
{
rt[i]=update(rt[i-1],1,n,id[i-1]);
}
// printf("%d\n",v[n]);
scanf("%d",&q);
int ans=0;
while(q--)
{
int l=1,r=n,t[5];
for(int i=1;i<=4;i++)
{
scanf("%d",&t[i]);
t[i]=(t[i]+ans)%n+1;
}
sort(t+1,t+5);
// printf("%d %d %d %d\n",t[1],t[2],t[3],t[4]);
while(l<r)
{
int mid=(l+r+1)>>1;
if(check(mid,t[1],t[2],t[3],t[4])) l=mid;
else r=mid-1;
// printf("%d %d\n",l,r);
}
ans=v[id[l]];
// printf("%d ",l);
printf("%d\n",ans);
}
return 0;
}
[cogs257] 动态排名系统
https://www.gxyzoj.com/d/gxyznoi/p/P10
树状数组套主席树
不带修的情况下就是对每个位置的值域去处理然后差分，如果暴力修改，每次就要做 \(n\) 次
所以可以只让一些节点储存 \(x\) 的信息，然后在合并就行了
所以可以按照树状数组的方法去存储和修改，这样就是 log 的了
点击查看代码
#include<cstdio>
#include<iostream>
using namespace std;
const int N=50005,Max=1e9,M=2e7;
int T,n,q,a[N],rt[N],ls[M],rs[M],val[M],tot;
int lowbit(int x)
{
return x & (-x);
}
int update(int p,int l,int r,int x,int v)
{
if(!p) p=++tot;
if(l==r)
{
val[p]+=v;
return p;
}
int mid=(l+r)>>1;
if(x<=mid) ls[p]=update(ls[p],l,mid,x,v);
else rs[p]=update(rs[p],mid+1,r,x,v);
val[p]=val[ls[p]]+val[rs[p]];
return p;
}
int lc[N],rc[N],cnt1,cnt2;
int query(int l,int r,int x)
{
if(l==r) return l;
int t=0,mid=(l+r)>>1;
for(int i=1;i<=cnt2;i++) t+=val[ls[rc[i]]];
for(int i=1;i<=cnt1;i++) t-=val[ls[lc[i]]];
if(t>=x)
{
for(int i=1;i<=cnt1;i++) lc[i]=ls[lc[i]];
for(int i=1;i<=cnt2;i++) rc[i]=ls[rc[i]];
return query(l,mid,x);
}
else
{
for(int i=1;i<=cnt1;i++) lc[i]=rs[lc[i]];
for(int i=1;i<=cnt2;i++) rc[i]=rs[rc[i]];
return query(mid+1,r,x-t);
}
}
void add(int id,int v)
{
int x=id;
while(x<=n)
{
rt[x]=update(rt[x],1,Max,a[id],-1);
x+=lowbit(x);
}
a[id]=v,x=id;
while(x<=n)
{
rt[x]=update(rt[x],1,Max,a[id],1);
x+=lowbit(x);
}
}
int getans(int l,int r,int x)
{
cnt1=cnt2=0;
while(l)
{
lc[++cnt1]=rt[l];
l-=lowbit(l);
}
while(r)
{
rc[++cnt2]=rt[r];
r-=lowbit(r);
}
return query(1,Max,x);
}
int main()
{
scanf("%d",&T);
while(T--)
{
for(int i=1;i<=tot;i++)
{
ls[i]=rs[i]=val[i]=0;
}
tot=0;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) rt[i]=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
int x=i;
while(x<=n)
{
rt[x]=update(rt[x],1,Max,a[i],1);
x+=lowbit(x);
}
}
while(q--)
{
char c;
int l,r,k;
cin>>c>>l>>r;
if(c=='C')
{
add(l,r);
}
else
{
cin>>k;
printf("%d\n",getans(l-1,r,k));
}
}
}
return 0;
}
七彩树
https://www.gxyzoj.com/d/gxyznoi/p/P143
如果没有深度的限制，考虑怎么做
首先，如果两个节点 u,v 在求的范围内，那么他们的 lca 必然也在这一范围内
所以可以先跑出 dfs 序，然后在 dfs 序的相邻节点的 lca 上 -1 即可
然后是层数的问题，按照层的编号建主席树即可
2.可持久化平衡树
首先得有一颗平衡树：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,idx,rt;
struct treap{
int val,rnd,siz,l,r;
}tr[100005];
void newnode(int &x,int v)
{
x=++idx;
tr[x].val=v;
tr[x].rnd=rand();
tr[x].siz=1;
}
void pushup(int p)
{
tr[p].siz=tr[tr[p].l].siz+tr[tr[p].r].siz+1;
}
void split(int p,int v,int &x,int &y)
{
if(!p)
{
x=y=0;
return;
}
if(tr[p].val<=v)
{
x=p;
split(tr[x].r,v,tr[x].r,y);
pushup(x);
}
else
{
y=p;
split(tr[y].l,v,x,tr[y].l);
pushup(y);
}
}
int merge(int x,int y)
{
if(!x||!y) return x+y;
if(tr[x].rnd<tr[y].rnd)
{
tr[x].r=merge(tr[x].r,y);
pushup(x);
return x;
}
else
{
tr[y].l=merge(x,tr[y].l);
pushup(y);
return y;
}
}
void insert(int v)
{
int x,y,z;
split(rt,v,x,y);
newnode(z,v);
rt=merge(merge(x,z),y);
}
void del(int v)
{
int x,y,z;
split(rt,v,x,z);
split(x,v-1,x,y);
y=merge(tr[y].l,tr[y].r);
rt=merge(merge(x,y),z);
}
int getrank(int v)
{
int x,y;
split(rt,v-1,x,y);
int ans=tr[x].siz+1;
rt=merge(x,y);
return ans;
}
int getval(int rt,int v)
{
if(v==tr[tr[rt].l].siz+1) return tr[rt].val;
else if(v<=tr[tr[rt].l].siz)
return getval(tr[rt].l,v);
else return getval(tr[rt].r,v-1-tr[tr[rt].l].siz);
}
int getpre(int v)
{
int x,y,s,ans;
split(rt,v-1,x,y);
s=tr[x].siz;
// printf("%d",)
ans=getval(x,s);
rt=merge(x,y);
return ans;
}
int getnxt(int v)
{
int x,y,ans;
split(rt,v,x,y);
// printf("%d %d\n",tr[x].siz,tr[y].siz);
ans=getval(y,1);
rt=merge(x,y);
return ans;
}
int main()
{
scanf("%d",&n);
while(n--)
{
int opt,x;
scanf("%d%d",&opt,&x);
if(opt==1) insert(x);
if(opt==2) del(x);
if(opt==3) printf("%d\n",getrank(x));
if(opt==4) printf("%d\n",getval(rt,x));
if(opt==5) printf("%d\n",getpre(x));
if(opt==6) printf("%d\n",getnxt(x));
}
return 0;
}
【模板】可持久化平衡树
https://www.gxyzoj.com/d/gxyznoi/p/133
可以发现，每一次会发生改变的部分就是分裂和合并的部分，会形成新的链，所以直接新开点记录即可
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+2,inf=2147483647;
int n,rt[N],idx;
struct treap{
int rnd,val,l,r,siz;
}tr[N*50];
void newnode(int &x,int v)
{
x=++idx;
tr[x].siz=1;
tr[x].val=v;
tr[x].rnd=rand();
}
void pushup(int p)
{
tr[p].siz=tr[tr[p].l].siz+tr[tr[p].r].siz+1;
}
void split(int p,int v,int &x,int &y)
{
if(!p)
{
x=y=0;
return;
}
if(tr[p].val<=v)
{
x=++idx,tr[x]=tr[p];
split(tr[x].r,v,tr[x].r,y);
pushup(x);
}
else
{
y=++idx,tr[y]=tr[p];
split(tr[y].l,v,x,tr[y].l);
pushup(y);
}
}
int merge(int x,int y)
{
if(!x||!y) return x+y;
int p=++idx;
if(tr[x].rnd>tr[y].rnd)
{
tr[p]=tr[x];
tr[p].r=merge(tr[p].r,y);
pushup(p);
}
else
{
tr[p]=tr[y];
tr[p].l=merge(x,tr[p].l);
pushup(p);
}
return p;
}
void insert(int id,int v)
{
int x,y,z;
split(rt[id],v,x,y);
newnode(z,v);
rt[id]=merge(merge(x,z),y);
}
void del(int id,int v)
{
int x,y,z;
split(rt[id],v,x,z);
split(x,v-1,x,y);
y=merge(tr[y].l,tr[y].r);
rt[id]=merge(merge(x,y),z);
}
int getrank(int id,int v)
{
int x,y;
split(rt[id],v-1,x,y);
int ans=tr[x].siz+1;
rt[id]=merge(x,y);
return ans;
}
int getval(int rt,int v)
{
if(v==tr[tr[rt].l].siz+1) return tr[rt].val;
else if(v<=tr[tr[rt].l].siz) return getval(tr[rt].l,v);
else return getval(tr[rt].r,v-tr[tr[rt].l].siz-1);
}
int getpre(int id,int v)
{
int x,y,s,ans;
split(rt[id],v-1,x,y);
s=tr[x].siz;
if(!s) return -inf;
ans=getval(x,s);
rt[id]=merge(x,y);
return ans;
}
int getnxt(int id,int v)
{
int x,y,ans;
split(rt[id],v,x,y);
if(!tr[y].siz) return inf;
ans=getval(y,1);
rt[id]=merge(x,y);
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int id,opt,x;
scanf("%d%d%d",&id,&opt,&x);
rt[i]=rt[id];
if(opt==1) insert(i,x);
if(opt==2) del(i,x);
if(opt==3) printf("%d\n",getrank(i,x));
if(opt==4) printf("%d\n",getval(rt[i],x));
if(opt==5) printf("%d\n",getpre(i,x));
if(opt==6) printf("%d\n",getnxt(i,x));
}
return 0;
}
【模板】可持久化文艺平衡树
就是上一道题的按值变为按下标，求和可以按照线段树的方法处理，但是反转涉及的点比较多
继续考虑线段树的处理方法，可以打懒标记，下放时交换左右儿子即可，但是因为要可持久化，所以下放时要复制儿子
[hdu6087]Rikka with Sequence
https://www.gxyzoj.com/d/gxyznoi/p/135
其实只有2个有用版本，即当前版和初版，但是它需要可持久化在于2操作相当于将一部分拿下来反复粘贴
为了避免复制的时间浪费，可持久化+倍增（就是快速幂写法）处理
3操作直接从原树上分裂然后粘上去就行了
但是这样空间显然不够，所以就需要定期将多出的几点删掉
点击查看代码
inline void dfs(int p)
{
if(!p) return;
tr[p].vis=cnt;
dfs(tr[p].l);
dfs(tr[p].r);
}
inline void rebuild()
{
cnt++;
dfs(rt),dfs(root);
int k=0;
for(int i=1;i<=num;i++)
{
if(tr[b[i]].vis==cnt) b[++k]=b[i];
else s[++top]=b[i];
}
num=k;
}
3.可持久化trie
和可持久化线段树相似，就是将字符串对应的链复制出来，然后+1
点击查看代码
void insert(int x,int v)
{
int now=++tot,p=rt[x-1];
rt[x]=tot,tr[now].cnt=x;
for(int i=30;i>=0;i--)
{
int tmp=((v>>i)&1);
tr[now].ch[tmp]=++tot;
tr[now].ch[tmp^1]=tr[p].ch[tmp^1];
p=tr[p].ch[tmp],now=tr[now].ch[tmp];
tr[now].cnt=tr[p].cnt+1;
}
}
int query(int l,int r,int k)
{
int x=rt[l-1],y=rt[r],ans=0;
for(int i=30;i>=0;i--)
{
int tmp=((k>>i)&1);
if(tr[tr[y].ch[tmp^1]].cnt-tr[tr[x].ch[tmp^1]].cnt)
{
ans+=(1<<i);
x=tr[x].ch[tmp^1],y=tr[y].ch[tmp^1];
}
else
{
x=tr[x].ch[tmp],y=tr[y].ch[tmp];
}
}
return ans;
}
最大异或和
https://www.gxyzoj.com/d/gxyznoi/p/P137
其实这个式子相当于求最大的 \(s_p\oplus s_n \oplus x(p=\{l-1,r-1\})\)
所以可以把前缀和放到字典树上，然后因为要作差判断是否存在，可持久化
[FOTILE模拟赛]L
看到段的异或和，直接前缀和处理
常理上讲可持久化trie必须要固定区间和所求值，但是因为题目要求的是区间中的区间，所以至少要枚举一个端点
所以如何减少枚举的数量，考虑分块
设 \(f_{i,j}\) 表示以第 j 块的左端点为起点，到点 i 这段区间的最大值
此时可以由 \(f_{i-1,j}\) 和以 i 为区间右端点的部分转移过来，散块暴力即可
[JSOI2015] 字符串树
https://www.gxyzoj.com/d/gxyznoi/p/P139
先考虑在数组上怎么做，显然可以建可持久化trie然后作差
然后是树上，因为串在边上，所以可以把他们全部挂在深度较大的点上，然后树剖即可
4.可持久化并查集
其实就是将 siz 和 fa 数组放到线段树上维护，然后进行单点修改单点查询
注意，这里不能路径压缩
P3402 可持久化并查集
https://www.gxyzoj.com/d/gxyznoi/p/144
点击查看代码
#include<cstdio>
using namespace std;
const int N=2e5+5;
int n,m,rt[N],ls[N*40],rs[N*40],siz[N*40],fa[N*40],tot;
inline int build(int p,int l,int r)
{
p=++tot;
if(l==r)
{
fa[p]=l,siz[p]=1;
return p;
}
int mid=(l+r)>>1;
ls[p]=build(ls[p],l,mid);
rs[p]=build(rs[p],mid+1,r);
return p;
}
inline int getsiz(int p,int l,int r,int x)
{
if(l==r) return siz[p];
int mid=(l+r)>>1;
if(x<=mid) return getsiz(ls[p],l,mid,x);
else return getsiz(rs[p],mid+1,r,x);
}
inline int getfa(int p,int l,int r,int x)
{
if(l==r) return fa[p];
int mid=(l+r)>>1;
if(x<=mid) return getfa(ls[p],l,mid,x);
else return getfa(rs[p],mid+1,r,x);
}
inline int update(int id,int l,int r,int x,int f,int s)
{
int p=++tot;
ls[p]=ls[id],rs[p]=rs[id];
if(l==r)
{
fa[p]=f,siz[p]=s;
return p;
}
int mid=(l+r)>>1;
if(x<=mid) ls[p]=update(ls[p],l,mid,x,f,s);
else rs[p]=update(rs[p],mid+1,r,x,f,s);
return p;
}
int f;
inline int find(int id,int x)
{
f=getfa(rt[id],1,n,x);
if(f!=x) f=find(id,f);
return f;
}
int main()
{
// freopen("P3402_14.in","r",stdin);
// freopen("1.txt","w",stdout);
scanf("%d%d",&n,&m);
rt[0]=build(0,1,n);
for(int i=1;i<=m;i++)
{
int opt,x,y;
// if() printf("%d",i);
scanf("%d%d",&opt,&x);
if(opt==2)
{
rt[i]=rt[x];
continue;
}
scanf("%d",&y);
rt[i]=rt[i-1];
if(opt==1)
{
int f1=find(i,x),f2=find(i,y);
int s1=getsiz(rt[i],1,n,f1),s2=getsiz(rt[i],1,n,f2);
if(f1==f2) continue;
if(s1>s2)
{
rt[i]=update(rt[i],1,n,f2,f1,s2);
rt[i]=update(rt[i],1,n,f1,f1,s2+s1);
}
else
{
rt[i]=update(rt[i],1,n,f1,f2,s1);
rt[i]=update(rt[i],1,n,f2,f2,s2+s1);
}
}
else
{
// printf("%d %d\n",find(i,x),find(i,y));
if(find(i,x)==find(i,y)) printf("1\n");
else printf("0\n");
}
}
return 0;
}
浙公网安备 33010602011771号