2777.txt

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

Problem Id:2777  User Id:fzk 
#include "stdio.h"
#include "memory.h"
int t[ 262144 ];
bool sign[262144];
int a, b, c;
void color( int l, int r, int k ) {
	int c = (l+r)/2, c1 = 2*k+1, c2 = 2*k+2;

	if( b <= l || r <= a )
		return;
	if( a<=l && r <= b ) {
		t[k] = ::c;
		sign[k] = true;
		return;
	}
	if( sign[k] ) {
		t[c1] = t[c2] = t[k];
		sign[c1] = sign[c2]  = true;
		sign[k] = false;
	}
	color( l, c, c1);
	color( c, r, c2);

	t[k] = ( t[c1] | t[c2] );
}
int query( int l, int r, int k ) {
	int c = (l+r)/2, c1 = 2*k+1, c2 = 2*k+2;
	if( b <= l || r <= a )
		return 0;
	if( a<=l && r <= b )
		return t[k];

	if( sign[k] )
		return t[k];
	return query( l, c, c1 ) | query( c, r, c2 );
}
int main( ) {
	int n, m, temp, ans;
	char cr[2];
	scanf( "%d %*d %d", &n, &m );
	memset( t, 0, sizeof t );
	memset( sign, 0, sizeof sign );
	
	t[0] = 1;
	sign[0] = true;
		
	while( m-- ) {
		scanf( "%1s", cr );
		if( cr[0] == 'C' ){
			scanf( "%d %d %d", &a, &b, &c );
			if( a > b ) {
				temp = a;
				a = b;
				b = temp;
			}
			a--;
			c = ( 1<<(c-1) );
			color( 0, 131072, 0 );
		}
		else {
			scanf( "%d %d", &a, &b );
			if( a > b ) {
				temp = a;
				a = b;
				b = temp;
			}
			a--;
			temp = query( 0, 131072, 0 );
			for( ans = 0; temp; temp /= 2 )
				if( temp & 1 )
					ans++;
			printf( "%d\n", ans );
		}
	}
	return 0;
}