首页 > 代码库 > HDU 5023 A Corrupt Mayor's Performance Art

HDU 5023 A Corrupt Mayor's Performance Art

 

HDU 5023 A Corrupt Mayor‘s Performance Art (线段树 + 状态压缩)

上周网络赛的B题,题目很长但是前面根本没有用
题意:线段树操作
P l r c      将 [l,r] 区间颜色换为 c
Q l r  查询 [l,r]区间一共有多少种颜色,并按升序输出
[ 初始状态墙壁颜色全部为2,总共30种颜色 ]

分析①: 考虑到最多30种颜色,可以直接用一个int型的变量来存放状态,32位正好
具体就是用线段树的成段更新,lazy为懒惰标记。注意下Query

  1 /* ***********************************************  2 Problem       :  3 File Name     :  4 Author        :  5 Created Time  :  6 ************************************************ */  7 //#define BUG  8 #include <cstdio>  9 #include <cstring> 10 #include <algorithm> 11 #include <map> 12 #include <vector> 13 #include <list> 14 #include <queue> 15 #include <ctime> 16 #include <iostream> 17 #include <cmath> 18 #include <set> 19 #include <string> 20 using namespace std; 21 typedef long long LL; 22 typedef unsigned long long ULL; 23 #define INF                 0x7fffffff 24 #define MAX                 0x3f3f3f3f 25  26 #define CLR( a, b )         memset( a, b, sizeof(a) ) 27 #define REP( i, a, b )      for( int i = (a); i < (b); ++i ) 28 #define FOR( i, a, b )      for( int i = (a); i <=(b); ++i ) 29 #define FOD( i, a, b )      for( int i = (a); i >=(b); --i ) 30 #define MID                 ( l + r ) >> 1 31 #define lson                l, m, o << 1 32 #define rson                m + 1, r, o << 1 | 1 33 #define ls                  o << 1 34 #define rs                  o << 1 | 1 35  36 #define MAXN                1010101 37  38 int lazy[MAXN << 2]; 39 int col[MAXN << 2]; 40  41 void PushUp( int o ) 42 { 43     col[o] = col[ls] | col[rs]; 44 } 45  46 void PushDown( int o ) 47 { 48     if( lazy[o] ) 49     { 50         lazy[ls] = lazy[o]; 51         lazy[rs] = lazy[o]; 52         col[ls] = col[rs] = lazy[o];//向下传递并直接修改col的值 53         lazy[o] = 0; 54     } 55 } 56  57 void Build( int l, int r, int o ) 58 { 59     if( l == r ) 60     { 61         col[o] = 1 << (2-1); 62         return; 63     } 64     int m = MID; 65     Build( lson ); 66     Build( rson ); 67     PushUp( o ); 68 } 69  70 void Update( int L, int R, int v, int l, int r, int o ) 71 { 72     if( L <= l && r <= R ) 73     { 74         lazy[o] = 1 << v; 75         col[o] = 1 << v; 76         return; 77     } 78     int m = MID; 79     PushDown( o ); 80     if(L <= m)  Update( L, R, v, lson ); 81     if(R >  m)  Update( L, R, v, rson ); 82     PushUp( o ); 83  84 } 85  86 int Query ( int L , int R , int l , int r , int o ) 87 { 88     if( L <= l && r <= R ) return col[o]; 89     int m = MID; 90     PushDown( o ); 91     if ( R <= m ) return Query ( L , R , lson ) ; 92     if ( m <  L ) return Query ( L , R , rson ) ; 93  94     return Query ( L , R , lson ) | Query ( L , R , rson ) ; 95 } 96  97  98 void Orz() 99 {100     int N,M;101     int l, r, co;102     char ch;103     while( ~scanf("%d%d",&N,&M) && (N+M) )104     {105         getchar();106         CLR( col, 0 ), CLR( lazy, 0 );107         Build(1,N,1);108         //Update(1,N,1,1,N,1);109         REP( i,0,M )110         {111             ch = getchar();112             if( ch == P )113             {114                 scanf( "%d %d %d", &l, &r, &co );115                 Update( l, r, co-1, 1, N, 1 );116             }117             else118             {119                 scanf( "%d %d", &l, &r );120                 int ans = Query(l,r,1,N,1);121                 int flag = 0;122                 REP( i, 0, 30 )123                 {124                     if( ans & (1 << i) )125                     {126                         if( flag )    printf(" ");127                         flag = 1;128                         printf( "%d", i + 1 );129                     }130                 }131                 puts("");132             }133             getchar();134         }135     }136 }137 138 139 int main()140 {141     #ifdef  BUG142         freopen( "in.txt", "r", stdin );143     #endif144     Orz();145     return 0;146 }
代码君
分析②: col[o] 存放当前线段内的颜色,

HDU 5023 A Corrupt Mayor's Performance Art