首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。