bzoj3673可持久化线段树实现可持久化数组实现可持久化并查集(好长)

线段树只用叶子节点感觉莫名浪费,,,

感觉真好写(刚从未来程序逃回来的人)

 #include <cstdio>
#define mid ((l+r)>>1)
int n,m,time,N=,ca,x,y;
int root[],ls[],rs[],a[];
int change(int x,int y)
{
int l=,r=n,now=++N,past=root[time];
root[++time]=N;
while(l!=r)
if(x<=mid) rs[now]=rs[past],ls[now]=++N,r=mid,now=ls[now],past=ls[past];
else ls[now]=ls[past],rs[now]=++N,l=mid+,now=rs[now],past=rs[past];
a[now]=y;
}
int que(int x)
{
int l=,r=n,now=root[time];
while(l!=r)
if(x<=mid) r=mid,now=ls[now];
else l=mid+,now=rs[now];
return a[now];
}
int get(int p)
{
for(int t=que(p);t!=p;t=que(p)) p=t;
return p;
}
int main()
{
scanf("%d%d",&n,&m);
root[time=]=;
for(int i=;i<=n;i++)
change(i,i);
int start=time;
for(int i=;i<=m;i++)
{
scanf("%d%d",&ca,&x);
if(ca==) root[++time]=root[x+start];
else
scanf("%d",&y),(ca==)?change(get(y),get(x)):(root[time+]=root[time++],printf("%d\n",get(x)==get(y)));
}
return ;
}
上一篇:[转帖]一文读懂 HTTP/2


下一篇:CentOS 6.3下部署LVS(NAT模式)+keepalived实现高性能高可用负载均衡