当前位置:编程学习 > C/C++ >>

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++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,