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
【分析】
出题人给我滚出来！保证不打死你！
真是***了，你题意描述清楚点会死啊。。调了将近2个小时...结果是题目理解错了....尼玛返回也算作操作啊。
思路还是蛮简单的。
用主席树维护一下并查集的fa数组就行了。
按照这种说法树状数组也应该可以可持久化了
/*
唐代李商隐
《无题·昨夜星辰昨夜风》 昨夜星辰昨夜风，画楼西畔桂堂东。
身无彩凤双飞翼，心有灵犀一点通。
隔座送钩春酒暖，分曹射覆蜡灯红。
嗟余听鼓应官去，走马兰台类转蓬。
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <utility>
#include <iomanip>
#include <string>
#include <cmath>
#include <queue>
#include <assert.h>
#include <map>
#include <ctime>
#include <cstdlib>
#include <stack>
#define LOCAL
const int MAXN = * * + ;
//const int MAXM = 20000 + 10;
const int INF = ;
const int SIZE = ;
const int maxnode = 0x7fffffff + ;
using namespace std;
int n, m;//n为元素总个数
struct SEGTREE{
//路径压缩+启发式合并还要用主席树OAO
struct Node{
Node *ch[];
int l, r;
int num;//其实除了叶子节点其他都是打酱油的,num是该节点的fa值
}mem[MAXN], *root[ * + ];
int tot; void init(){
tot = ;
root[] = NULL;
for (int i = ; i <= * ; i++) root[i] = NULL;
build(root[], , n);
//printf("%d %d\n", root[0]->ch[0]->l, root[0]->ch[0]->r);
}
Node *NEW(int l, int r){
Node *p = &mem[tot++];
p->l = l;
p->r = r;
p->num = -;
p->ch[] = p->ch[] = NULL;
return p;
}
void build(Node *&t, int l, int r){
if (t == NULL){
t = NEW(l, r);
//不要返回
}
if (l == r) return;
int mid = (l + r) >> ;
build(t->ch[], l, mid);
build(t->ch[], mid + , r);
}
//t为现在的数将x的num改为val
void insert(Node *&t, Node *&last, int x, int val){
if (t == NULL){
t = NEW(last->l, last->r);
}
if (t->l == x && t->r == x) {t->num = val; return;}
int mid = (t->l + t->r) >>;
if (x <= mid){
insert(t->ch[], last->ch[], x, val);
t->ch[] = last->ch[];
}
if (x > mid){
insert(t->ch[], last->ch[], x, val);
t->ch[] = last->ch[];
}
}
//直接修改,不是可持久化的,节省空间
/*void change(Node *&t, int x, int val){
if (t->l == x && t->r == x) {t->num = val;return;}
int mid = (t->l + t->r) >> 1;
if (x <= mid) change(t->ch[0], x, val);
if (x > mid) change(t->ch[1], x, val);
}*/
int get(int k, int x){//查找k时刻x的fa值
Node *t = root[k];
while (){
if (t->l == x && t->r == x) break;
int mid = (t->l + t->r) >> ;
if (x <= mid) t = t->ch[];
else t = t->ch[];
}
return t->num;
}
}A;
int data[MAXN];//真正的操作次数
int cnt = ;//cnt记录现在的状态
int BIGCNT; int find(int x){
int tmp = A.get(cnt, x);
if (tmp < ) return x;
else{
int tmp2 = find(tmp);
//A.insert(A.root[cnt + 1], A.root[cnt], x, tmp2);
//cnt++;
return tmp2;
}
}
//启发式合并
void merge(int x, int y){
//分别代表真实数量
int x_num = -A.get(cnt, x);
int y_num = -A.get(cnt ,y);
if (x_num > y_num){//将y合并到x上
//这里可以可持久化了
//A.root[cnt + 1] = NULL;
A.insert(A.root[BIGCNT + ], A.root[cnt], x, -(x_num + y_num));
BIGCNT++;
//A.root[cnt + 1] = NULL;
A.insert(A.root[BIGCNT + ], A.root[cnt], y, x);
BIGCNT++;
}else{
//A.root[cnt + 1] = NULL;
A.insert(A.root[BIGCNT + ], A.root[cnt], y, -(x_num + y_num));
BIGCNT++;
//A.root[cnt + 1] = NULL;
A.insert(A.root[BIGCNT + ], A.root[cnt], x, y);
BIGCNT++;
//printf("%d %d %d\n", x, y, find(x));
}
}
void work(){
int z = ;//记录操作的
data[] = ;
cnt = ;
BIGCNT = ;
scanf("%d%d", &n, &m);
A.init();
for (int i = ; i <= m; i++){
int t;
scanf("%d", &t);
if (t == ){
int c;
scanf("%d", &c);//回到c时刻即操作之后
if (c == )
printf("");
cnt = data[c];
}else if (t == ){
int a, b;
scanf("%d%d", &a, &b);
int xa = find(a), xb = find(b);
if (xa == xb) {data[i] = cnt;continue;}
merge(xa, xb);
cnt = BIGCNT;
}else{
int a, b;
scanf("%d%d", &a, &b);
if (find(a) == find(b)) printf("1\n");
else printf("0\n");
}
data[i] = cnt;
}
//printf("%d", data[6]);
} int main(){ work();
return ;
}