BZOJ 3673: 可持久化并查集 by zky
正文索引 [隐藏]
Description
n个集合 m个操作
操作：
1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合，是则输出1否则输出0
0<n,m<=2*10^4
操作：
1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合，是则输出1否则输出0
0<n,m<=2*10^4
Input
Output
Sample Input
5 6
1 1 2
3 1 2
2 0
3 1 2
2 1
3 1 2
1 1 2
3 1 2
2 0
3 1 2
2 1
3 1 2
Sample Output
1
1
1
题解
Orz昨天电脑屏幕莫名坏掉了、一定是因为昨天开了三连击WIFI、、
今天立马换了一个旧电脑和机械键盘Orz、
可持久化线段树维护数组做并查集、
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 |
/* Author:WNJXYK WebSite:http://wnjxyk.cn Weibo:http://weibo.com/WNJXYK */ #include<cstdio> using namespace std; struct BTree{ int lt,rt; int deep; int left,right; int val; }; const int Maxn=2000005; BTree tree[Maxn]; int tot; void build(int &x,int left,int right){ if (!x) x=++tot; tree[x].left=left; tree[x].right=right; if (left==right){ tree[x].val=left; tree[x].deep=1; return; } int mid=(left+right)/2; build(tree[x].lt,left,mid); build(tree[x].rt,mid+1,right); } inline void copyTree(int x,int y){ tree[y].left=tree[x].left; tree[y].right=tree[x].right; tree[y].val=tree[x].val; tree[y].lt=tree[x].lt; tree[y].rt=tree[x].rt; tree[y].deep=tree[x].deep; } void modify(int &y,int x,int pos,int val){ y=++tot; copyTree(x,y); if (tree[x].left==tree[x].right){ tree[y].val=val; }else{ int mid=(tree[x].left+tree[x].right)/2; if (pos<=mid) modify(tree[y].lt,tree[x].lt,pos,val); if (mid+1<=pos) modify(tree[y].rt,tree[x].rt,pos,val); } } inline void add(int x,int pos){ if (tree[x].left==tree[x].right){ tree[x].deep++; }else{ int mid=(tree[x].left+tree[x].right)/2; if (pos<=mid) add(tree[x].lt,pos); if (mid+1<=pos) add(tree[x].rt,pos); } } int query(int x,int pos){ if (tree[x].left==tree[x].right){ return x; }else{ int mid=(tree[x].left+tree[x].right)/2; if (pos<=mid) return query(tree[x].lt,pos); else return query(tree[x].rt,pos); } } int find(int k,int x){ int p=query(k,x); if (tree[p].val==x) return p; return find(k,tree[p].val); } int n,m; int root[200005]; inline void swap(int &a,int &b){ int tmp=a; a=b; b=tmp; } int main(){ scanf("%d%d",&n,&m); //root[0]=1; build(root[0],1,n); for (int i=1;i<=m;i++){ int k,a,b; scanf("%d",&k); if (k==1){ root[i]=root[i-1]; scanf("%d%d",&a,&b); int fa=find(root[i],a),fb=find(root[i],b); if (tree[fa].val==tree[fb].val) continue; if (tree[fa].deep>tree[fb].deep) swap(fa,fb); modify(root[i],root[i-1],tree[fa].val,tree[fb].val); if (tree[fa].deep==tree[fb].deep) add(root[i],tree[fa].val); } if (k==2){ scanf("%d",&a); root[i]=root[a]; } if (k==3){ root[i]=root[i-1]; scanf("%d%d",&a,&b); int fa=find(root[i],a),fb=find(root[i],b); if (tree[fa].val==tree[fb].val){ printf("1n"); }else{ printf("0n"); } } } return 0; } |
原文链接：BZOJ 3673: 可持久化并查集 by zky
WNJXYKの博客 版权所有，转载请注明出处。
orzorz
llr超强！