The k-th Largest Group
Time Limit:2000MS? Memory Limit:131072K
Total Submit:1222 Accepted:290

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.

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
POJ Monthly--2006.08.27, zcgzcgzcg

#include? < iostream >
using ? namespace ?std;
const ? int ?MAXN? = ? 200001 ;

class ?UFset
{
public :
???? int ?parent[MAXN];
????UFset();
???? int ?Find( int );
???? void ?Union( int ,? int );
} ;

UFset::UFset()
{
????memset(parent,? - 1 ,? sizeof (parent));
}

int ?UFset::Find( int ?x)
{
???? if ?(parent[x]? < ? 0 )
???????? return ?x;
???? else
???? {
????????parent[x]? = ?Find(parent[x]);
???????? return ?parent[x];
????} // ?壓縮路徑
}

void ?UFset::Union( int ?x,? int ?y)
{
???? int ?pX? = ?Find(x);
???? int ?pY? = ?Find(y);
???? int ?tmp;
???? if ?(pX? != ?pY)
???? {
????????tmp? = ?parent[pX]? + ?parent[pY];? // ?加權合并
???????? if ?(parent[pX]? > ?parent[pY])
???????? {
????????????parent[pX]? = ?pY;
????????????parent[pY]? = ?tmp;
????????}
???????? else
???????? {
????????????parent[pY]? = ?pX;
????????????parent[pX]? = ?tmp;
????????}
????}
}

int ?f[(MAXN + 1 ) * 3 ]? = ? { 0 } ;
int ?n,?m;

void ?initTree()
{
???? int ?l? = ? 1 ,?r? = ?n;
???? int ?c? = ? 1 ;
???? while ?(l? < ?r)
???? {
????????f[c]? = ?n;
????????c? = ?c? * ? 2 ;
????????r? = ?(l? + ?r)? / ? 2 ;
????}
????f[c]? = ?n; // 葉子初始化
}

void ?insertTree( int ?k)
{
???? int ?l? = ? 1 ,?r? = ?n;
???? int ?c? = ? 1 ;
???? int ?mid;

???? while ?(l? < ?r)
???? {
????????f[c] ++ ;
????????mid? = ?(r? + ?l)? / ? 2 ;
???????? if ?(k? > ?mid)
???????? {
????????????l? = ?mid? + ? 1 ;
????????????c? = ?c? * ? 2 ? + ? 1 ;
????????}
???????? else
???????? {
????????????r? = ?mid;
????????????c? = ?c? * ? 2 ;
????????}
????}
????f[c] ++ ; // 葉子增加1
}

void ?delTree( int ?k)
{
???? int ?l? = ? 1 ,?r? = ?n;
???? int ?c? = ? 1 ;
???? int ?mid;

???? while ?(l? < ?r)
???? {
????????f[c] -- ;
????????mid? = ?(r? + ?l)? / ? 2 ;
???????? if ?(k? > ?mid)
???????? {
????????????l? = ?mid? + ? 1 ;
????????????c? = ?c? * ? 2 ? + ? 1 ;
????????}
???????? else
???????? {
????????????r? = ?mid;
????????????c? = ?c? * ? 2 ;
????????}
????}
????f[c] -- ; // 葉子減少1
}

int ?searchTree( int ?k)
{
???? int ?l? = ? 1 ,?r? = ?n;
???? int ?c? = ? 1 ;
???? int ?mid;

???? while ?(l? < ?r)
???? {
????????mid? = ?(l? + ?r)? / ? 2 ;
???????? if ?(k? <= ?f[ 2 * c + 1 ])
???????? {
????????????l? = ?mid? + ? 1 ;
????????????c? = ?c? * ? 2 ? + ? 1 ;
????????}
???????? else
???????? {
????????????k? -= ?f[ 2 * c + 1 ];
????????????r? = ?mid;
????????????c? = ?c? * ? 2 ;
????????}
????}
???? return ?l;
}

int ?main()
{
???? int ?i,?j;
???? int ?x,?y;
???? int ?k;
???? int ?l,?r;
???? int ?cmd;
???? int ?px,?py;
???? int ?tx,?ty,?tz;
????UFset?UFS;

????
????scanf( " %d%d " ,? & n,? & m);
????initTree();
???? for ?(i = 0 ;?i < m;?i ++ )
???? {
????????scanf( " %d " ,? & cmd);
???????? if ?(cmd? == ? 0 )
???????? {
????????????scanf( " %d%d " ,? & x,? & y);
????????????px? = ?UFS.Find(x);
????????????py? = ?UFS.Find(y);
???????????? if ?(px? != ?py)
???????????? {
????????????????tx? = ? - UFS.parent[px];
????????????????ty? = ? - UFS.parent[py];
????????????????tz? = ?tx? + ?ty;
????????????????UFS.Union(x,?y);
????????????????insertTree(tz);
????????????????delTree(tx);
????????????????delTree(ty);
????????????}
????????}
???????? else
???????? {
????????????scanf( " %d " ,? & k);
????????????printf( " %d\n " ,?searchTree(k));
????????}
????}
???? return ? 0 ;
}