2985.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:2985  User Id:fzk 
Memory:3160K  Time:701MS
Language:C++  Result:Accepted

Source 

#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 %d\n", 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( "%d\n", get( 0, n+1, 0 ) );
		}
	}
	return 0;
}