Description
Newman likes playing with cats. He possesses lots of cats in his home. Because the number of cats is really huge, Newman wants to group some of the cats. To do that, he first offers a number to each of the cat (1, 2, 3, …, n). Then he occasionally combines the group cat i is in and the group cat j is in, thus creating a new group. On top of that, Newman wants to know the size of the k-th biggest group at any time. So, being a friend of Newman, can you help him?
Input
1st line: Two numbers N and M (1 ≤ N, M ≤ 200,000), namely the number of cats and the number of operations.
2nd to (m + 1)-th line: In each line, there is number C specifying the kind of operation Newman wants to do. If C = 0, then there are two numbers i and j (1 ≤ i, j ≤ n) following indicating Newman wants to combine the group containing the two cats (in case these two cats are in the same group, just do nothing); If C = 1, then there is only one number k (1 ≤ k ≤ the current number of groups) following indicating Newman wants to know the size of the k-th largest group.
Output
For every operation “1” in the input, output one number per line, specifying the size of the kth largest group.
Sample Input
10 10
0 1 2
1 4
0 3 4
1 2
0 5 6
1 1
0 7 8
1 1
0 9 10
1 1
Sample Output
1
2
2
2
2
Hint
When there are three numbers 2 and 2 and 1, the 2nd largest number is 2 and the 3rd largest number is 1.
Source
#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> const int N = + ;
const int SIZE = ;//块状链表的大小
const int M = + ;
using namespace std;
struct TREAP{
struct Node{
int fix, size;
int val;
Node *ch[];
}mem[N], *root;
struct mem_poor{//内存池
queue<Node>Q;
void push(Node *t){//消除指针t所占用的地址
Q.push((*t));
}
Node* get(){
Node* t = &Q.front();
Q.pop();
return t;
}
}poor;
int tot, size;
//大随机
void init(){
// for (int i = 0; i <= 200000 + 5; i++)
//poor.Q.push(mem[i]);
size = ;
tot = ;
}
int BIG_RAND(){return rand();}
Node *NEW(){
Node *p = new Node;
p->fix = rand();//BIG_RAND();
p->size = ;
p->ch[] = p->ch[] = NULL;
return p;
}
//将t的d节点换到t
void rotate(Node *&t, int d){
Node *p = t->ch[d];
t->ch[d] = p->ch[d ^ ];
p->ch[d ^ ] = t;
t->size = ;
if (t->ch[] != NULL) t->size += t->ch[]->size;
if (t->ch[] != NULL) t->size += t->ch[]->size;
p->size = ;
if (p->ch[] != NULL) p->size += p->ch[]->size;
if (p->ch[] != NULL) p->size += p->ch[]->size;
t = p;
return;
}
void insert(Node *&t, int val){
//插入
if (t == NULL){
t = NEW();
t->val = val;
//size++;
return;
}
//大的在右边,小的在左边
int dir = (val >= t->val);
insert(t->ch[dir], val);
//维护最大堆的性质
if (t->ch[dir]->fix > t->fix) rotate(t, dir);
t->size = ;
if (t->ch[] != NULL) t->size += t->ch[]->size;
if (t->ch[] != NULL) t->size += t->ch[]->size;
}
//在t的子树中找到第k小的值
int kth(Node *t, int k){
if (t == NULL || k<= || k > t -> size) return ;
if (t->size == ) return t->val;
int l = ;//t的左子树中有多少值
if (t->ch[] != NULL) l += t->ch[]->size;
if (k == (l + )) return t->val;
if (k <= l) return kth(t->ch[], k);
else return kth(t->ch[], k - (l + ));
}
/*int find(Node *t, int val){
if (t == NULL) return 0;
int l = 0;//累加值
if (t->ch[0] != NULL) l += t->ch[0]->size;
if (val == t->val) return l + 1;
else if (val < t->val) return find(t->ch[0], val);
else return l + 1 + find(t->ch[1], val);
}*/
//找到值为val的节点
/*Node *&get(Node *&t, int val){
//if (t == NULL) return NULL;
if (val == t->val) return t;//根结点是，没办法 if (t->ch[0] != NULL && t->ch[0]->val == val) return t;
if (t->ch[1] != NULL && t->ch[1]->val == val) return t; if (val < t->val) return get(t->ch[0], val);
else return get(t->ch[1], val);
}*/
/*void update(Node *&t){
if (t == NULL) return;
update(t->ch[0]);
update(t->ch[1]);
t->size = 1;
if (t->ch[0] != NULL) t->size += t->ch[0]->size;
if (t->ch[1] != NULL) t->size += t->ch[1]->size;
}*/
void Delete(Node* &t,int x){
int d;
if (x == t->val) d = -;
else d = (x > t->val);
if (d == -){
Node *tmp = t;
if(t->ch[] == NULL){
t = t->ch[];
//poor.push(tmp);
delete tmp;
tmp = NULL;
}else if(t->ch[] == NULL){
t = t->ch[];
//poor.push(tmp);
delete tmp;
tmp = NULL;
}else{
int k = t->ch[]->fix > t->ch[]->fix ? : ;
//int k = 1;
rotate(t,k);
Delete(t->ch[k ^ ],x);
}
}else Delete(t->ch[d],x);
if (t!=NULL){
t->size = ;
if (t->ch[] != NULL) t->size += t->ch[]->size;
if (t->ch[] != NULL) t->size += t->ch[]->size;
}
}
/*void print(Node *t){
if (t == NULL) return;
print(t->ch[0]);
printf("%d ", t->val);
print(t->ch[1]);
}*/
}treap;
/*int Scan() {
int res = 0, ch, flag = 0;
if((ch = getchar()) == '-') //判断正负
flag = 1;
else if(ch >= '0' && ch <= '9') //得到完整的数
res = ch - '0';
while((ch = getchar()) >= '0' && ch <= '9' )
res = res * 10 + ch - '0';
return flag ? -res : res;
} */
int parent[N], n ,m;
int find(int x){return parent[x] < ? x : parent[x] = find(parent[x]);} void init(){
treap.init();
treap.root = NULL;
//memset(parent, -1, sizeof(parent));
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++) parent[i] = -;
//n = Scan();
//m = Scan();
//for (int i = 1; i <= n; i++) treap.insert(treap.root, 1);
}
void work(){
for (int i = ; i <= m; i++){
int t;
//t = Scan();
scanf("%d", &t);
if (t == ){
int x, y;
scanf("%d%d", &x, &y);
//x = Scan();y = Scan();
x = find(x);
y = find(y);
if (x == y) continue;
if (parent[x] < -) treap.Delete(treap.root, -parent[x]);
if (parent[y] < -) treap.Delete(treap.root, -parent[y]);
treap.insert(treap.root, -(parent[x] + parent[y]));
parent[y] += parent[x];
parent[x] = y;
}else{
int k;
scanf("%d", &k);
//k = Scan();i
if (treap.root == NULL || k > treap.root->size) {printf("1\n");continue;}
k = treap.root->size - k + ;
printf("%d\n", treap.kth(treap.root, k));
}
}
} int main(){
int T;
srand(time());
#ifdef LOCAL
freopen("data.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
init();
work();
//debug();
return ;
}