首页 > 代码库 > BZOJ 3674 可持久化并查集加强版（主席树变形）
BZOJ 3674 可持久化并查集加强版（主席树变形）
3673: 可持久化并查集 by zky
Time Limit: 5 Sec Memory Limit: 128 MBSubmit: 2515 Solved: 1107
[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
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
0
1
0
1
HINT
Source
出题人大SB
题目链接：BZOJ 3674
原来并查集也是可以可持久化的，其思想应该是在于用可持久化数据结构来维护一个前缀记录，由于普通的并查集一开始每一个节点的祖先都是本身，因此要多一个建树的操作，把所有的叶子节点的祖先都处理好，然后这题是并查集，并不需要差分的思想，也就是说更新或者查询只需要用到一个root点，其他的做法跟普通的并查集差不多，详细的可以看黄大牛的博客：http://hzwer.com/3997.html。
代码：
#include <bits/stdc++.h>using namespace std;#define INF 0x3f3f3f3f#define LC(x) (x<<1)#define RC(x) ((x<<1)+1)#define MID(x,y) ((x+y)>>1)#define CLR(arr,val) memset(arr,val,sizeof(arr))#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);typedef pair<int, int> pii;typedef long long LL;const double PI = acos(-1.0);const int N = 2e5 + 7;struct seg{ int lson, rson; int pre;};seg T[N * 40];int root[N], tot;int n;void init(){ CLR(root, 0); tot = 0;}void build(int &cur, int l, int r){ cur = ++tot; T[cur].lson = T[cur].rson = 0; if (l == r) T[cur].pre = l; else { int mid = MID(l, r); build(T[cur].lson, l, mid); build(T[cur].rson, mid + 1, r); }}void update(int &cur, int ori, int l, int r, int pos, int pre){ cur = ++tot; T[cur] = T[ori]; if (l == r) { T[cur].pre = pre; return ; } else { int mid = MID(l, r); if (pos <= mid) update(T[cur].lson, T[ori].lson, l, mid, pos, pre); else update(T[cur].rson, T[ori].rson, mid + 1, r, pos, pre); }}int query(int k, int l, int r, int pos) //返回子节点位置{ if (l == r) return k; else { int mid = MID(l, r); if (pos <= mid) return query(T[k].lson, l, mid, pos); else return query(T[k].rson, mid + 1, r, pos); }}int Find(int k, int pre){ int idx = query(k, 1, n, pre); if (pre == T[idx].pre) return pre; else return Find(k, T[idx].pre);}int main(void){ int m, i, a, b, k, ops; while (~scanf("%d%d", &n, &m)) { init(); int ans = 0; build(root[0], 1, n); for (i = 1; i <= m; ++i) { scanf("%d", &ops); if (ops == 1) { scanf("%d%d", &a, &b); a ^= ans; b ^= ans; root[i] = root[i - 1]; int fa = Find(root[i], a); int fb = Find(root[i], b); if (fa != fb) update(root[i], root[i - 1], 1, n, fb, fa); } else if (ops == 2) { scanf("%d", &k); k ^= ans; root[i] = root[k]; } else if (ops == 3) { scanf("%d%d", &a, &b); a ^= ans; b ^= ans; root[i] = root[i - 1]; int fa = Find(root[i], a); int fb = Find(root[i], b); printf("%d\n", ans = (fa == fb)); } } } return 0;}BZOJ 3674 可持久化并查集加强版（主席树变形）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。