「BZOJ3674」可持久化并查集加强版
Description
Description：
自从zkysb出了可持久化并查集后……
hzwer:乱写能AC，暴力踩标程
KuribohG：我不路径压缩就过了！
ndsf：暴力就可以轻松虐！
zky:……
n个集合 m个操作
操作：
1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合，是则输出1否则输出0
请注意本题采用强制在线,所给的a,b,k均经过加密,加密方法为x = x xor lastans,lastans的初始值为0
0<n,m<=2*10^5
Sample Input
5 6
1 1 2
3 1 2
2 1
3 0 3
2 1
3 1 2
1 1 2
3 1 2
2 1
3 0 3
2 1
3 1 2
Sample Output
1
0
1
0
1
题解
听说zky把我的做法卡了2333
然后我T的停不下来。。。注意看了眼题目，诶强制在线。。。
再次T的停不下来T T，开大了空间准备开始写路径压缩，恩先随手交一下吧。。。
诶A掉了
原来是zky大神卡我程序忘记开大数组了T T
|
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 |
#include<cstdio> #include<iostream> using namespace std; inline int read() { int x=0;char ch=getchar(); while(ch>'9'||ch<'0')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int n,m,sz,last; int root[200005],ls[10000005],rs[10000005],v[10000005],deep[10000005]; void build(int &k,int l,int r) { if(!k)k=++sz; if(l==r){v[k]=l;return;} int mid=(l+r)>>1; build(ls[k],l,mid); build(rs[k],mid+1,r); } void modify(int l,int r,int x,int &y,int pos,int val) { y=++sz; if(l==r){v[y]=val;deep[y]=deep[x];return;} ls[y]=ls[x];rs[y]=rs[x]; int mid=(l+r)>>1; if(pos<=mid) modify(l,mid,ls[x],ls[y],pos,val); else modify(mid+1,r,rs[x],rs[y],pos,val); } int query(int k,int l,int r,int pos) { if(l==r)return k; int mid=(l+r)>>1; if(pos<=mid)return query(ls[k],l,mid,pos); else return query(rs[k],mid+1,r,pos); } void add(int k,int l,int r,int pos) { if(l==r){deep[k]++;return;} int mid=(l+r)>>1; if(pos<=mid)add(ls[k],l,mid,pos); else add(rs[k],mid+1,r,pos); } int find(int k,int x) { int p=query(k,1,n,x); if(x==v[p])return p; return find(k,v[p]); } int main() { n=read();m=read(); build(root[0],1,n); int f,k,a,b; for(int i=1;i<=m;i++) { f=read(); if(f==1) { root[i]=root[i-1]; a=read();b=read();a=a^last;b=b^last; int p=find(root[i],a),q=find(root[i],b); if(v[p]==v[q])continue; if(deep[p]>deep[q])swap(p,q); modify(1,n,root[i-1],root[i],v[p],v[q]); if(deep[p]==deep[q])add(root[i],1,n,v[q]); } if(f==2) {k=read();k=k^last;root[i]=root[k];} if(f==3) { root[i]=root[i-1]; a=read();b=read();a=a^last;b=b^last; int p=find(root[i],a),q=find(root[i],b); if(v[p]==v[q])last=1; else last=0; printf("%d\n",last); } } return 0; } |
发现似乎加上路径压缩之后时间变慢了T T
|
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 |
#include<cstdio> #include<iostream> using namespace std; inline int read() { int x=0;char ch=getchar(); while(ch>'9'||ch<'0')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int n,m,sz,last; int root[200005],ls[10000005],rs[10000005],v[10000005],deep[10000005]; void build(int &k,int l,int r) { if(!k)k=++sz; if(l==r){v[k]=l;return;} int mid=(l+r)>>1; build(ls[k],l,mid); build(rs[k],mid+1,r); } void modify(int l,int r,int x,int &y,int pos,int val) { y=++sz; if(l==r){v[y]=val;deep[y]=deep[x];return;} ls[y]=ls[x];rs[y]=rs[x]; int mid=(l+r)>>1; if(pos<=mid) modify(l,mid,ls[x],ls[y],pos,val); else modify(mid+1,r,rs[x],rs[y],pos,val); } int query(int k,int l,int r,int pos) { if(l==r)return k; int mid=(l+r)>>1; if(pos<=mid)return query(ls[k],l,mid,pos); else return query(rs[k],mid+1,r,pos); } void add(int k,int l,int r,int pos) { if(l==r){deep[k]++;return;} int mid=(l+r)>>1; if(pos<=mid)add(ls[k],l,mid,pos); else add(rs[k],mid+1,r,pos); } int find(int k,int x) { int p=query(k,1,n,x); if(x==v[p])return p; int t=find(k,v[p]); modify(1,n,k,k,v[p],t); return t; } int main() { n=read();m=read(); build(root[0],1,n); int f,k,a,b; for(int i=1;i<=m;i++) { f=read(); if(f==1) { root[i]=root[i-1]; a=read();b=read();a=a^last;b=b^last; int p=find(root[i],a),q=find(root[i],b); if(v[p]==v[q])continue; if(deep[p]>deep[q])swap(p,q); modify(1,n,root[i-1],root[i],v[p],v[q]); if(deep[p]==deep[q])add(root[i],1,n,v[q]); } if(f==2) {k=read();k=k^last;root[i]=root[k];} if(f==3) { root[i]=root[i-1]; a=read();b=read();a=a^last;b=b^last; int p=find(root[i],a),q=find(root[i],b); if(v[p]==v[q])last=1; else last=0; printf("%d\n",last); } } return 0; } |
计数器 9774529
OI 课件=>
OI 课件=>
黄学长：请问只写启发式合并和只写路径压缩哪个更快？还有启发式合并的关键字不是最长链的长度吗（考虑最劣情况）？
srO谢谢Orz
数据使然？由于你每次都是启发式合并所以最长链长度不科学吧
然而每次相当于插入一个点，感觉和子树大小没啥关系。。
都是启发式合并啊，合出来的东西就像个满二叉树
貌似无所谓……路径压缩好像根本没用
其实是出题人没有卡掉。
只需要按秩合并，是卡不掉的
只要把多出来的log卡掉就行了（不过可能会不小心把正解卡掉？）
T T 这个不好卡吧
说实话再丧心病狂一点可以这样：把只用路径压缩||只用按秩合并的全部卡掉……不过为了noip还是攒点人品吧（其实是我自己弱造不出这样的数据）
这样仅仅是理论复杂度减小了T T
然而Noip2015 Day2T3的理论复杂度。。。
噗……原来用您的程序卡的时候忘开大数组了，我果然是真·弱逼