题解 P1558 【色板游戏】

kradcigam

2020-06-14 18:02:27

Solution

这道题目,我们发现 $1\leq t\leq 30$,$t$ 的值非常小。 考虑建 $t$ 棵线段树,每颗线段树维护是否有这种颜色,需要区间全部清零和区间全部赋值。 我使用的是封装数据结构,注释写的很清楚了 ```cpp #include <bits/stdc++.h> #define ls num<<1 #define rs num<<1|1 using namespace std; typedef long long ll; template<typename T>inline void read(T &FF){ T RR=1;FF=0;char CH=getchar(); for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1; for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48); FF*=RR; } const int MAXN=1e5+10; int a[MAXN]; struct Line_Tree{ struct Tree{ int l,r,lazy;//lazy:1为区间赋值,2为区间清零 bool f; }t[MAXN<<2]; void pushup(int num){ t[num].f=(t[ls].f||t[rs].f);//只要有一个部分有这种颜色,就说明这个区间有这种颜色。 } void pushdown(int num){ if(t[num].lazy){ t[ls].lazy=t[rs].lazy=t[num].lazy;//lazy的传递,由于是区间覆盖,所以直接赋值 t[ls].f=t[rs].f=(t[num].lazy==1);//1为区间赋值,2为区间清零 t[num].lazy=0; } } void build(int num,int l,int r,int x){ t[num].l=l;t[num].r=r;t[num].lazy=false; if(l==r){ t[num].f=(a[l]==x);//显然QAQ return;//直接return }int mid=(l+r)>>1; build(ls,l,mid,x); build(rs,mid+1,r,x); pushup(num);//注意pushup } void change1(int num,int l,int r){ if(t[num].l>=l&&t[num].r<=r){ t[num].lazy=1;//打标记 t[num].f=true;//直接操作 return;//直接return }pushdown(num);//注意标记下传 if(t[ls].r>=l)change1(ls,l,r); if(t[rs].l<=r)change1(rs,l,r); pushup(num);//注意pushup } void change2(int num,int l,int r){ if(t[num].l>=l&&t[num].r<=r){ t[num].lazy=2;//打标记 t[num].f=false;//直接操作 return;//直接return }pushdown(num);//注意标记下传 if(t[ls].r>=l)change2(ls,l,r); if(t[rs].l<=r)change2(rs,l,r); pushup(num);//注意pushup } bool query(int num,int l,int r){ if(t[num].l>=l&&t[num].r<=r)return t[num].f;//直接看 pushdown(num);//注意标记下传 if(t[ls].r<l)return query(rs,l,r); if(t[rs].l>r)return query(ls,l,r); return (query(ls,l,r)||query(rs,l,r));//只要有一个是就是了 } }T[32];//线段树 int main(){ int n,t,E;read(n);read(t);read(E); for(int i=1;i<=n;i++)a[i]=1;//初始化 for(int i=1;i<=t;i++)T[i].build(1,1,n,i);//初始化 while(E--){ char f=getchar();int a,b,c; for(;f!='C'&&f!='P';)f=getchar(); read(a);read(b);if(a>b)swap(a,b); if(f=='C'){ read(c); for(int i=1;i<=t;i++)//枚举颜色 if(i==c)T[i].change1(1,a,b);//区间赋值 else T[i].change2(1,a,b);//区间清零 }else{ int s=0;//计数器 for(int i=1;i<=t;i++)//枚举颜色 if(T[i].query(1,a,b))s++;//如果有这种颜色 printf("%d\n",s);//输出 } } return 0; } ```