Poj Solution 2985

http://poj.org/problem?id=2985

#include "stdio.h"
#include "memory.h"


int tree[600000];

int k, key;
void set( int l, int r, int s ) {
    int c = (l+r)/2;
    
    tree[s] += key;
    
    if( r == l+1 )
        return;
    if( k < c )
        set( l, c, s*2+1 );
    else
        set( c, r, s*2+2 );
}

int get( int l, int r, int s ) {
    int c = (l+r)/2;
//    printf( "%d %d %dn", l, r, tree[s] );
    if( r == l+1 )
        return l;
    
    if( tree[s*2+1] >= k )
        return get( l, c, s*2+1 );
    else {
        k -= tree[s*2+1];
        return get( c, r, s*2+2 );
    }
}

int p[200100], n, m;
int st[200100], sn;

int find( int k ) {
     for( sn=0; p[k] >= 0; k = p[k] )
         st[sn++] = k;
     while( sn-- )
         p[ st[sn] ] = k;
     return k;
}

void merge( int a, int b ) {
    key = -1;
        
    k = -p[a];
    set( 0, n+1, 0 );
    k = -p[b];
    set( 0, n+1, 0 );
    
    k = -p[a]-p[b];
    key = 1;
    set( 0, n+1, 0 );
    
    if( -p[a] < -p[b] )
        p[a] = b, p[b] = -k;
    else
        p[b] = a, p[a] = -k;
}

int main( ) {
    int i, j, c, h;
    scanf( "%d%d", &n, &m );
    memset( tree, 0, sizeof tree );
    memset( p, -1, sizeof p );
    
    key = n;
    k=1;
    set( 0, n+1, 0 );
    h = n;
    
    while( m-- ) {
        scanf( "%d", &c );
        if( c == 0 ) {
            scanf( "%d%d", &i, &j );
            i = find(i);
            j = find(j);
            if( i != j ) {
                merge( i, j );
                h--;
            }
        }
        else {
            scanf( "%d", &k );
            k = h-k+1;
            printf( "%dn", get( 0, n+1, 0 ) );
        }
    }
    return 0;
}