poj2985The k-th Largest Group

リンク:http://poj.org/problem?id=2985
題意:最初にn個の要素の個数が1の集合を与えて、それからm個の操作を与えて、2種類の操作があります:C=0の時にaを入力して、bはa、bのありかの集合を1つの集合にまとめることを表して、C=1の時にkを入力して現在のすべての集合の中で集合の大きさの並べ替えの中でk番目に大きい集合のsizeを尋ねることを表します.
分析:集合を統合して直接使用し、セットを調べてメンテナンスすればいいのですが、k番目に大きいものを探すには木状の配列でk番目に大きいものを探せばいいのです.
コード:

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<math.h>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int N=200010;
const int MAX=151;
const int mod=100000000;
const int MOD1=100000007;
const int MOD2=100000009;
const double EPS=0.00000001;
typedef long long ll;
const ll MOD=1000000009;
const ll INF=10000000010;
typedef double db;
typedef unsigned long long ull;
int n,f[N],g[N],p[N];
void add(int x,int y) {
    for (;x<=n;x+=x&(-x)) p[x]+=y;
}
int sum(int x) {
    int ret=0;
    for (;x;x-=x&(-x)) ret+=p[x];
    return ret;
}
int ask_k(int k) {
    int i,w=0;
    for (i=20;i>=0;i--)
    if (w+(1<<i)<=n&&p[w+(1<<i)]<k) {
        k-=p[w+(1<<i)];w+=1<<i;
    }
    return w+1;
}
int find_f(int x) {
    return f[x]==x ? x:f[x]=find_f(f[x]);
}
int main()
{
    int a,b,c,k,i,m,tot;
    scanf("%d%d", &n, &m);
    memset(p,0,sizeof(p));
    for (i=1;i<=n;i++) f[i]=i,g[i]=1;
    add(1,n);tot=n;
    while (m--) {
        scanf("%d", &c);
        if (!c) {
            scanf("%d%d", &a, &b);
            int fa=find_f(a),fb=find_f(b);
            if (fa!=fb) {
                tot--;add(g[fa],-1);add(g[fb],-1);
                f[fa]=fb;g[fb]+=g[fa];add(g[fb],1);
            }
        } else {
            scanf("%d", &k);
            printf("%d
", ask_k(tot-k+1));
        }
    }
    return 0;
}