poj 2777Count Color

注意：a可能比b大
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #define maxn 1000010
  5 using namespace std;
  6 
  7 int  T,L,O,a,b,c;
  8 char ch;
  9 struct node
 10 {
 11     int l,r,co;
 12 }tree[3*maxn];
 13 bool tab[31];
 14 
 15 void build(int l,int r,int i)
 16 {
 17     tree[i].co=1;
 18     tree[i].l=l;tree[i].r=r;
 19     if(l<r)
 20     {
 21         int mid=(l+r)/2;
 22         build(l,mid,i+i);
 23         build(mid+1,r,i+i+1);
 24     }
 25 }
 26 
 27 void update(int i)
 28 {
 29     if(tree[i].co>0)
 30     {
 31         tree[i+i].co=tree[i+i+1].co=tree[i].co;
 32     }
 33     tree[i].co=-1;
 34 }
 35 
 36 void insert1(int i,int l,int r,int co)
 37 {
 38     if(tree[i].l>=l&&tree[i].r<=r)
 39     {
 40         tree[i].co=co;
 41         return ;
 42     }
 43     if(tree[i].l>r||tree[i].r<l) return ;
 44     if(tree[i].l<tree[i].r)
 45     {
 46         int mid=(tree[i].l+tree[i].r)/2;
 47         update(i);
 48         if(r<=mid) insert1(i+i,l,r,co);
 49         else if(l>mid) insert1(i+i+1,l,r,co);
 50         else
 51         {
 52             insert1(i+i,l,mid,co);
 53             insert1(i+i+1,mid+1,r,co);
 54         }
 55     }
 56 }
 57 
 58 void serch(int l,int r,int i)
 59 {
 60     if(tree[i].co>0)
 61     {
 62         tab[tree[i].co]=true;
 63         return ;
 64     }
 65     if(tree[i].l<tree[i].r)
 66     {
 67         int mid=(tree[i].l+tree[i].r)/2;
 68         if(r<=mid) serch(l,r,i+i);
 69         else if(l>mid) serch(l,r,i+i+1);
 70         else
 71         {
 72             serch(l,mid,i+i);
 73             serch(mid+1,r,i+i+1);
 74         }
 75     }
 76 }
 77 int main()
 78 {
 79     scanf("%d%d%d",&L,&T,&O);
 80     getchar();
 81     build(1,L,1);
 82     while(O--)
 83     {
 84         scanf("%c",&ch);
 85         if(ch=='C')
 86         {
 87             scanf("%d%d%d",&a,&b,&c);
 88             if(a>b)
 89                 swap(a,b);
 90             insert1(1,a,b,c);
 91         }
 92         else if(ch=='P')
 93         {
 94             scanf("%d%d",&a,&b);
 95             memset(tab,false,sizeof(tab));
 96             if(a>b) swap(a,b);
 97             serch(a,b,1);
 98             int num=0;
 99             for(int i=1; i<=T; i++)
100             {
101                 if(tab[i]) num++;
102             }
103             printf("%d
",num);
104         }
105         getchar();
106     }
107     return 0;
108 }
View Code