POJ 2777 Count Color

线段树。各种WA。最后过了，老泪纵横。
View Code
  1 #include <stdio.h>
  2 #define MAXN 100001
  3 int col[MAXN * 4],lazy[MAXN * 4];
  4 void update(int cur)
  5 {
  6     col[cur] = col[cur << 1] | col[cur << 1 | 1];
  7 }
  8 
  9 void pushdown(int cur,int x,int y)
 10 {
 11     int mid = (x + y) >> 1,ls = cur << 1,rs = cur << 1 | 1;
 12     if(lazy[cur] != -1)
 13     {
 14         lazy[ls] = lazy[cur];
 15         lazy[rs] = lazy[cur];
 16         col[ls] = lazy[cur];
 17         col[rs] = lazy[cur];
 18         lazy[cur] = -1;
 19     }
 20 }
 21 
 22 void build(int cur,int x,int y)
 23 {
 24     int mid = (x + y) >> 1,ls = cur << 1,rs = cur << 1 | 1;
 25     lazy[cur] = -1;
 26     if(x == y)
 27     {
 28         col[cur] = 1;
 29         return;
 30     }
 31     build(ls,x,mid);
 32     build(rs,mid + 1,y);
 33     update(cur);
 34 }
 35 
 36 void change(int cur,int x,int y,int s,int t,int c)
 37 {
 38     int mid = (x + y) >> 1,ls = cur << 1,rs = cur << 1 | 1;
 39     if(x >= s && y <= t)
 40     {
 41         col[cur] = c;
 42         lazy[cur] = c;
 43         return;
 44     }
 45     pushdown(cur,x,y);
 46     if(mid >= s)
 47         change(ls,x,mid,s,t,c);
 48     if(mid + 1 <= t)
 49         change(rs,mid + 1,y,s,t,c);
 50     update(cur);
 51 }
 52 
 53 void query(int cur,int x,int y,int s,int t,int &ans)
 54 {
 55     int mid = (x + y) >> 1,ls = cur << 1,rs = cur << 1 | 1;
 56     
 57     if(x >= s && y <= t)
 58     {
 59         ans |= col[cur];
 60         return;
 61     }
 62     pushdown(cur,x,y);
 63     if(mid >= s)
 64         query(ls,x,mid,s,t,ans);
 65     if(mid + 1 <= t)
 66         query(rs,mid + 1,y,s,t,ans);
 67     //update(cur);    
 68 }
 69 
 70 int cal(int a)
 71 {
 72     int ans = 0;
 73     while(a)
 74     {
 75         if(a % 2)
 76             ans++;
 77         a >>= 1;
 78     }
 79     return ans;
 80 }
 81 
 82 int main()
 83 {
 84     int L,O,T,a,b,c,ans,temp;
 85     char ch;
 86     while(scanf("%d%d%d",&L,&T,&O) == 3)
 87     {
 88         build(1,1,L);
 89         while(O--)
 90         {
 91             /*printf("\n");
 92             for(int i = 0;i <= L * 4;i++)
 93                 printf("%d   ",col[i]);
 94             printf("\n");*/
 95             getchar();
 96             scanf("%c",&ch);
 97             if(ch == 'C')
 98             {
 99                 scanf("%d%d%d",&a,&b,&c);
100                 if(a > b)
101                 {
102                     temp = a;
103                     a = b;
104                     b = temp;
105                 }
106                 change(1,1,L,a,b,1 << (c - 1));
107             }
108             else
109             {
110                 scanf("%d%d",&a,&b);
111                 if(a > b)
112                 {
113                     temp = a;
114                     a = b;
115                     b = temp;
116                 }
117                 ans = 0;
118                 query(1,1,L,a,b,ans);
119                 printf("%d\n",cal(ans));
120             }
121             /*printf("\n");
122             for(int i = 0;i <= L * 4;i++)
123                 printf("%d   ",col[i]);
124             printf("\n");
125             for(int i = 0;i <= L * 4;i++)
126                 printf("%d ",lazy[i]);
127             printf("\n");*/
128         }
129     }
130     return 0;
131 }