3673: 可持久化并查集 by zky
Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 1878 Solved: 846
[Submit][Status][Discuss]
Description
n个集合 m个操作
操作：
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
1 1 2
3 1 2
2 0
3 1 2
2 1
3 1 2
Sample Output
0
1
HINT
Source
3674: 可持久化并查集加强版
Time Limit: 15 Sec Memory Limit: 256 MB
Submit: 2367 Solved: 886
[Submit][Status][Discuss]
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
Input
Output
Sample Input
1 1 2
3 1 2
2 1
3 0 3
2 1
3 1 2
Sample Output
0
1
HINT
Source
Solution
先说离线的一种思路，以前yveh做Codeforces的时候告诉我一道题，与之类似，存在一个状态退回到第多少步，当时是需要线段树维护一个东西，所以可以形成一个树形结构，然后dfs并回溯离线做。
但是这里并不能那么搞，因为并查集不支持删除所以没法回溯，所以只能考虑令并查集的 代表元素数组可持久化
所以本质上都得用可持久化数据结构维护代表元素数组，就无所谓离线在线了。
具体的做法就是建可持久化线段树，每次修改就在线段树上建一个新的链，叶子节点维护的是这个点的代表元素，所以方法很简单就是先初始化建出一棵新的树，然后每次新建一条链即可。
然后这里就剩下一个问题了，就是并查集$find$，为了保证复杂度，我采用了路径压缩但这里发现路径压缩会使树上操作数增多，建很多新的节点，所以常数比较大，然后看了hxy和zyf的代码，发现她们都和hzwer写的一样，采用的按秩合并，不过常数比我还大，不过显而易见 如果不加优化一定会TLE，所以二选一即可，并无太大的差距。
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
inline int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define MAXN 500010
int N,M,last;
namespace PrTree
{
int sz,lson[MAXN*],rson[MAXN*],root[MAXN],f[MAXN*];
inline void Insert(int l,int r,int &now,int fa,int pos,int val)
{
now=++sz;
if (l==r) {f[now]=val; return;}
int mid=(l+r)>>;
lson[now]=lson[fa],rson[now]=rson[fa];
if (pos<=mid) Insert(l,mid,lson[now],lson[fa],pos,val);
else Insert(mid+,r,rson[now],rson[fa],pos,val);
}
inline int Query(int l,int r,int pos,int now)
{
if (l==r) return f[now];
int mid=(l+r)>>;
if (pos<=mid) return Query(l,mid,pos,lson[now]);
else return Query(mid+,r,pos,rson[now]);
}
inline void BuildTree(int l,int r,int &now)
{
now=++sz;
if (l==r) {f[now]=l; return;}
int mid=(l+r)>>;
BuildTree(l,mid,lson[now]); BuildTree(mid+,r,rson[now]);
}
}using namespace PrTree;
inline int F(int x,int &rt) {int fa; if ((fa=Query(,N,x,rt))==x) return x; else return Insert(,N,rt,rt,x,fa=F(fa,rt)),fa;}
inline void Merge(int x,int y,int &rt) {int fx=F(x,rt),fy=F(y,rt); if (fx!=fy) Insert(,N,rt,rt,fx,fy);}
int main()
{
N=read(),M=read();
BuildTree(,N,root[]);
for (int i=; i<=M; i++)
{
root[i]=root[i-];
int opt=read(),x,y;
switch (opt)
{
case : x=read(),y=read(); x^=last,y^=last; Merge(x,y,root[i]); break;
case : x=read(); x^=last; root[i]=root[x]; break;
case : x=read(),y=read(); x^=last,y^=last; printf("%d\n",last=(F(x,root[i])==F(y,root[i]))); break;
}
}
return ;
}
总体来说写起来还是蛮好写的，就是自己开始手误，在可持久化线段树的时候 左右都下放的lson，然后瞪着屏幕20分钟才看出来...