# 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;
}
```
This entry was posted in poj. Bookmark the permalink.