Count Color(线段树)

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <algorithm>
  4 #define lson l,mid,rt<<1
  5 #define rson mid+1,r,rt<<1|1
  6 using namespace std;
  7 const int N=100010;
  8 struct node
  9 {
 10     int l,r,color;
 11 } Tree[N*4];
 12 bool vis[N];
 13 void build(int l,int r,int rt)
 14 {
 15     Tree[rt].l = l;
 16     Tree[rt].r = r;
 17     Tree[rt].color = 1;
 18     if(l==r)
 19         return;
 20     int mid = (l+r)>>1;
 21     build(lson);
 22     build(rson);
 23 }
 24 void pushdow(int rt)//标记传递
 25 {
 26     if (Tree[rt].color > 0)//有标记才传递，题中color值非负，小于0时表示没有标记
 27     {
 28         Tree[2*rt].color=Tree[2*rt+1].color = Tree[rt].color;
 29     }
 30     Tree[rt].color = -1;//清除本节点标记
 31 }
 32 void Insert(int l,int r,int rt,int c)
 33 {
 34     if (Tree[rt].l>=l&&Tree[rt].r<=r)//当前节点完全包含在查询区间内
 35     {
 36         Tree[rt].color = c;//直接修改当前节点的颜色
 37         return ;
 38     }
 39     if(Tree[rt].r<l||Tree[rt].l>r)//不合法的区间
 40         return ;
 41     int mid = (Tree[rt].r+Tree[rt].l)>>1;
 42     pushdow(rt);//将当前节点的值向下传递
 43     if(r<=mid)
 44         Insert(l,r,2*rt,c);
 45     else if (l > mid)
 46         Insert(l,r,2*rt+1,c);
 47     else
 48     {
 49         Insert(lson,c);
 50         Insert(rson,c);
 51     }
 52 }
 53 void Search(int l,int r,int rt)
 54 {
 55     if (Tree[rt].color>0)
 56     {
 57         vis[Tree[rt].color] = true;//标记[l,r]中所用的颜色
 58         return ;
 59     }
 60     int mid = (Tree[rt].l+Tree[rt].r)>>1;
 61     if(r <= mid)
 62         Search(l,r,2*rt);
 63     else if (l > mid)
 64         Search(l,r,2*rt+1);
 65     else
 66     {
 67         Search(lson);
 68         Search(rson);
 69     }
 70 }
 71 int main()
 72 {
 73     int L,T,O,l,r,c;
 74     scanf("%d%d%d",&L,&T,&O);
 75     build(1,L,1);
 76     while(O--)
 77     {
 78         char s[3];
 79         scanf("%s",s);
 80         if (s[0]==‘C‘)
 81         {
 82             scanf("%d%d%d",&l,&r,&c);
 83             if (l > r)
 84                 swap(l,r);
 85             Insert(l,r,1,c);
 86         }
 87         else
 88         {
 89             memset(vis,0,sizeof(vis));
 90             scanf("%d%d",&l,&r);
 91             if (l > r)
 92                 swap(l,r);
 93             Search(l,r,1);
 94             int ans = 0;
 95             for (int i = 1; i <= T; i++)
 96             {
 97                 if (vis[i])
 98                     ans++;
 99             }
100             printf("%d\n",ans);
101         }
102     }
103     return 0;
104 }