首页 > 代码库 > POJ2777

POJ2777

2024-07-20 13:39:39   217人阅读

题目大意：

在一段长度为n的黑板上按区间涂色，询问某段区间内不同颜色的数量

这里颜色涂改我们很难区分，但因为这里至多只有30种颜色，所以我们可以利用2进制数来代表颜色的个数

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 #define N 100005 7 int sum; 8 struct node{ 9     int color;10     bool cover;11     int x,y;12 }node[N<<2];13 void push_up(int o)14 {15     node[o].color=node[o<<1].color|node[o<<1|1].color;16     if(node[o<<1].cover&&node[o<<1|1].cover&&node[o<<1].color==node[o<<1|1].color)17         node[o].cover=true,node[o].color=node[o<<1].color;18 }19 void push_down(int o)20 {21     int ls=o<<1,rs=o<<1|1;22     if(node[o].cover){23         node[ls].cover=node[rs].cover=true;24         node[ls].color=node[o].color;25         node[rs].color=node[o].color;26         node[o].cover=false;27     }28 }29 void build(int o,int x,int y)30 {31     int mid=(x+y)/2,ls=o<<1,rs=o<<1|1;32     node[o].cover=true;33     node[o].color=1;34     node[o].x=x,node[o].y=y;35     if(x==y) return;36     build(ls,x,mid);37     build(rs,mid+1,y);38 }39 void update(int o,int s,int t,int v)40 {41     int mid=(node[o].x+node[o].y)/2,ls=o<<1,rs=o<<1|1;42     if(node[o].x>=s&&node[o].y<=t){43         node[o].cover=true;44         node[o].color=v;45         return;46     }47     push_down(o);48     if(mid>=s) update(ls,s,t,v);49     if(mid<t)  update(rs,s,t,v);50     push_up(o);51 }52 void query(int o,int s,int t)53 {54     int mid=(node[o].x+node[o].y)/2,ls=o<<1,rs=o<<1|1;55     if(node[o].x>=s&&node[o].y<=t){56         sum|=node[o].color;57         return;58     }59     push_down(o);60     if(mid>=s) query(ls,s,t);61     if(mid<t)  query(rs,s,t);62 }63 int countbit(int x)64 {65     int k=0;66     while(x){67         if(x&1) k++;68         x>>=1;69     }70     return k;71 }72 int main()73 {74     int n,t,Q,a,b,c;75     char str[5];76     while(~scanf("%d%d%d",&n,&t,&Q)){77         build(1,1,n);78         while(Q--){79             scanf("%s%d%d",str,&a,&b);80             if(a>b) swap(a,b);81             if(str[0]==‘C‘){82                 scanf("%d",&c);83                 update(1,a,b,1<<(c-1));84                 //cout<<"haha"<<endl;85             }86             else{87                 sum=0;88                 query(1,a,b);89                 printf("%d\n",countbit(sum));90             }91         }92     }93     return 0;94 }

 

POJ2777


联系
我们