首页 > 代码库 > [BZOJ3674]可持久化并查集加强版&[BZOJ3673]可持久化并查集 by zky
[BZOJ3674]可持久化并查集加强版&[BZOJ3673]可持久化并查集 by zky
思路：
用主席树维护并查集森林，每次连接时新增结点。
似乎并不需要启发式合并，我随随便便写了一个就跑到了3674第一页？
3673是这题的弱化版，本来写个暴力就能过，现在借用加强版的代码（去掉异或），直接吊打暴力程序。
1 #include<cstdio> 2 #include<cctype> 3 inline int getint() { 4 register char ch; 5 while(!isdigit(ch=getchar())); 6 register int x=ch^‘0‘; 7 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^‘0‘); 8 return x; 9 }10 const int N=200001,SIZE=3850000;11 class PresistentDisjointSet {12 private:13 unsigned int left[SIZE],right[SIZE],sz;14 int anc[SIZE];15 unsigned int newnode() {16 return sz++;17 }18 unsigned int getpos(const unsigned int p,const int b,const int e,const int x) {19 if(b==e) return p;20 int mid=(b+e)>>1;21 return (x<=mid)?getpos(left[p],b,mid,x):getpos(right[p],mid+1,e,x);22 }23 public:24 unsigned int root[N];25 PresistentDisjointSet() {26 sz=0;27 }28 void Build(unsigned int &p,const int b,const int e) {29 p=newnode();30 if(b==e) {31 anc[p]=b;32 return;33 }34 int mid=(b+e)>>1;35 Build(left[p],b,mid);36 Build(right[p],mid+1,e);37 }38 unsigned int find(const unsigned int p,const int b,const int e,const int x) {39 int q=getpos(p,b,e,x);40 return x==anc[q]?q:find(p,b,e,anc[q]);41 }42 unsigned int Union2(const unsigned int p,const int b,const int e,const int x,const int y) {43 unsigned int new_p=newnode();44 if(b==e) {45 anc[new_p]=y;46 return new_p;47 }48 int mid=(b+e)>>1;49 if(x<=mid) left[new_p]=Union2(left[p],b,mid,x,y),right[new_p]=right[p];50 if(x>mid) right[new_p]=Union2(right[p],mid+1,e,x,y),left[new_p]=left[p];51 return new_p;52 }53 bool isConnected(const int x,const int y) {54 return anc[x]==anc[y];55 }56 unsigned int Union(const unsigned int p,const int b,const int e,int x,int y) {57 x=find(p,b,e,x),y=find(p,b,e,y);58 if(isConnected(x,y)) return p;59 return Union2(p,b,e,anc[x],anc[y]);60 }61 };62 PresistentDisjointSet s;63 int main() {64 int n=getint(),lastans=0;65 s.Build(s.root[0],1,n);66 int m=getint();67 for(register int i=1;i<=m;i++) {68 int op=getint();69 if(op==1) s.root[i]=s.Union(s.root[i-1],1,n,getint()^lastans,getint()^lastans);70 else if(op==2) s.root[i]=s.root[getint()^lastans];71 else s.root[i]=s.root[i-1],printf("%d\n",lastans=s.isConnected(s.find(s.root[i],1,n,getint()^lastans),s.find(s.root[i],1,n,getint()^lastans)));72 }73 return 0;74 }
[BZOJ3674]可持久化并查集加强版&[BZOJ3673]可持久化并查集 by zky
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。