区间染色问题，用线段树可以解决。颜色总类不多，故考虑用二进制数的每一位表示一种颜色，然后父节点的颜色就是孩子节点颜色“或”起来，加上lazy标记，轻松AC。
poj 2777：
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 6 const int N = 100001; 7 8 struct Node 9 { 10 int l, r, color; 11 bool lazy; 12 } node[N << 2]; 13 14 void build( int i, int l, int r ) 15 { 16 node[i].l = l, node[i].r = r, node[i].color = 1, node[i].lazy = false; 17 if ( l == r ) return ; 18 int mid = ( l + r ) >> 1; 19 build( i << 1, l, mid ); 20 build( i << 1 | 1, mid + 1, r ); 21 } 22 23 void pushup( int i ) 24 { 25 node[i].color = ( node[i << 1].color | node[i << 1 | 1].color ); 26 } 27 28 void pushdown( int i ) 29 { 30 if ( node[i].lazy ) 31 { 32 node[i].lazy = false; 33 int lc = i << 1, rc = lc | 1; 34 node[lc].lazy = node[rc].lazy = true; 35 node[lc].color = node[rc].color = node[i].color; 36 } 37 } 38 39 void update( int i, int l, int r, int c ) 40 { 41 if ( node[i].l == l && node[i].r == r ) 42 { 43 node[i].lazy = true; 44 node[i].color = c; 45 return ; 46 } 47 pushdown(i); 48 int mid = ( node[i].l + node[i].r ) >> 1; 49 if ( r <= mid ) 50 { 51 update( i << 1, l, r, c ); 52 } 53 else if ( l > mid ) 54 { 55 update( i << 1 | 1, l, r, c ); 56 } 57 else 58 { 59 update( i << 1, l, mid, c ); 60 update( i << 1 | 1, mid + 1, r, c ); 61 } 62 pushup(i); 63 } 64 65 int query( int i, int l, int r ) 66 { 67 if ( node[i].l == l && node[i].r == r ) 68 { 69 return node[i].color; 70 } 71 pushdown(i); 72 int mid = ( node[i].l + node[i].r ) >> 1; 73 if ( r <= mid ) 74 { 75 return query( i << 1, l, r ); 76 } 77 else if ( l > mid ) 78 { 79 return query( i << 1 | 1, l, r ); 80 } 81 else 82 { 83 int la = query( i << 1, l, mid ); 84 int ra = query( i << 1 | 1, mid + 1, r ); 85 return ( la | ra ); 86 } 87 } 88 89 int main () 90 { 91 int l, t, o; 92 while ( scanf("%d%d%d", &l, &t, &o) != EOF ) 93 { 94 build( 1, 1, l ); 95 char op[2]; 96 int a, b, c; 97 while ( o-- ) 98 { 99 scanf("%s", op); 100 if ( op[0] == 'C' ) 101 { 102 scanf("%d%d%d", &a, &b, &c); 103 if ( a > b ) swap( a, b ); 104 c = ( 1 << ( c - 1 ) ); 105 update( 1, a, b, c ); 106 } 107 else 108 { 109 scanf("%d%d", &a, &b); 110 if ( a > b ) swap( a, b ); 111 int ans = query( 1, a, b ), cnt = 0; 112 while ( ans ) 113 { 114 if ( ans & 1 ) 115 { 116 cnt++; 117 } 118 ans >>= 1; 119 } 120 printf("%d ", cnt); 121 } 122 } 123 } 124 return 0; 125 }
hdu 5316（和poj 2777基本一样）：
1 #include <cstring> 2 #include <cstdio> 3 using namespace std; 4 5 const int N = 1000001; 6 7 struct Node 8 { 9 int l, r, color; 10 bool lazy; 11 } node[N << 2]; 12 13 void build( int i, int l, int r ) 14 { 15 node[i].l = l, node[i].r = r, node[i].color = 2, node[i].lazy = false; 16 if ( l == r ) return ; 17 int mid = ( l + r ) >> 1; 18 build( i << 1, l, mid ); 19 build( i << 1 | 1, mid + 1, r ); 20 } 21 22 void pushup( int i ) 23 { 24 node[i].color = ( node[i << 1].color | node[i << 1 | 1].color ); 25 } 26 27 void pushdown( int i ) 28 { 29 if ( node[i].lazy ) 30 { 31 node[i].lazy = false; 32 int lc = i << 1, rc = lc | 1; 33 node[lc].lazy = node[rc].lazy = true; 34 node[lc].color = node[rc].color = node[i].color; 35 } 36 } 37 38 void update( int i, int l, int r, int c ) 39 { 40 if ( node[i].l == l && node[i].r == r ) 41 { 42 node[i].lazy = true; 43 node[i].color = c; 44 return ; 45 } 46 pushdown(i); 47 int mid = ( node[i].l + node[i].r ) >> 1; 48 if ( r <= mid ) 49 { 50 update( i << 1, l, r, c ); 51 } 52 else if ( l > mid ) 53 { 54 update( i << 1 | 1, l, r, c ); 55 } 56 else 57 { 58 update( i << 1, l, mid, c ); 59 update( i << 1 | 1, mid + 1, r, c ); 60 } 61 pushup(i); 62 } 63 64 int query( int i, int l, int r ) 65 { 66 if ( node[i].l == l && node[i].r == r ) 67 { 68 return node[i].color; 69 } 70 pushdown(i); 71 int mid = ( node[i].l + node[i].r ) >> 1; 72 if ( r <= mid ) 73 { 74 return query( i << 1, l, r ); 75 } 76 else if ( l > mid ) 77 { 78 return query( i << 1 | 1, l, r ); 79 } 80 else 81 { 82 int la = query( i << 1, l, mid ); 83 int ra = query( i << 1 | 1, mid + 1, r ); 84 return ( la | ra ); 85 } 86 } 87 88 int main () 89 { 90 int n, m; 91 while ( scanf("%d%d", &n, &m) != EOF ) 92 { 93 if ( n == 0 && m == 0 ) break; 94 build( 1, 1, n ); 95 char op[2]; 96 int a, b, c; 97 while ( m-- ) 98 { 99 scanf("%s", op); 100 if ( op[0] == 'P' ) 101 { 102 scanf("%d%d%d", &a, &b, &c); 103 c = ( 1 << ( c - 1 ) ); 104 update( 1, a, b, c ); 105 } 106 else 107 { 108 scanf("%d%d", &a, &b); 109 int ans = query( 1, a, b ), cnt = 0, oo[30]; 110 for ( int i = 0; i < 30; i++ ) 111 { 112 if ( ans & ( 1 << i ) ) 113 { 114 oo[cnt++] = i + 1; 115 } 116 } 117 for ( int i = 0; i < cnt; i++ ) 118 { 119 printf("%d", oo[i]); 120 if ( i != cnt - 1 ) putchar(' '); 121 else putchar(' '); 122 } 123 } 124 } 125 } 126 return 0; 127 }