Count Color
线段树,染色问题// 3d.cpp : 定义控制台应用程序的入口点。 // //#include "stdafx.h" #include<iostream> #include<cstdio> #include<cmath> 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 ); } printf( "%d\n", ans ); } } } return 0; }
补充:软件开发 , C++ ,