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.
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
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
;
}
posted on 2006-09-06 13:28
豪 阅读(801)
评论(4) 编辑 收藏 引用 所属分类:
ACM题目