線段樹，染色問題
?
// 3d.cpp : 定義控制臺應用程序的入口點，
Count Color
。//
//#include "stdafx.h"
#include
#include
#include
using namespace std;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
const int maxn = 200005;
int sum[ maxn << 2 ], Add[ maxn << 2 ];
void PushUp( int rt ){
sum[ rt ] = ( sum[ rt << 1 ] | sum[ rt << 1 | 1 ] );
}
void PushDown( int rt ){
if( Add[ rt ] != 0 ){
Add[ rt << 1 ] = Add[ rt << 1 | 1 ] = Add[ rt ];
sum[ rt << 1 ] = sum[ rt << 1 | 1 ] = sum[ rt ];
Add[ rt ] = 0;
}
}
void Build( int l, int r, int rt ){
Add[ rt ] = 0;
sum[ rt ] = 1;
if( l == r ){
return;
}
int m = ( l + r ) >> 1;
Build( lson );
Build( rson );
PushUp( rt );
}
void Update( int L, int R, int temp, int l, int r, int rt ){
if( L <= l && r <= R ){
Add[ rt ] = 1;
sum[ rt ] = temp;
return;
}
PushDown( rt );
int m = ( l + r ) >> 1;
if( L <= m ){
Update( L, R, temp, lson );
}
if( R > m ){
Update( L, R, temp, rson );
}
PushUp( rt );
}
int Query( int L, int R, int l, int r, int rt ){
if( L == l && r == R ){
return sum[ rt ];
}
PushDown( rt );
int m = ( l + r ) >> 1;
int ans = 0;
if( R <= m )
ans = Query( L, R, lson );
else if( L > m )
ans = Query( L, R, rson );
else
ans = ( Query( L, m, lson ) | Query( m + 1, R, rson ) );
return ans;
}
//int _tmain(int argc, _TCHAR* argv[])
int main()
{
int n, m, k, a, b, c;
char str[ 10 ];
while( scanf( "%d%d%d", &n, &m, &k ) != EOF ){
Build( 1, n, 1 );
while( k-- ){
scanf( "%s", str );
if( str[ 0 ] == 'C' ){
scanf( "%d%d%d", &a, &b, &c );
Update( a, b, 1 << ( c - 1 ), 1, n, 1 );
}
else{
scanf( "%d%d", &a, &b );
if( a > b )
swap( a, b);
int temp = Query( a, b, 1, n, 1 );
int ans = 0;
while( temp ){
if( temp % 2 != 0 )
ans++;
temp = ( temp >> 1 );
}