题解 P1558 【色板游戏】
小菜鸟
2019-09-29 19:10:20
~~已经忘记线段树的平衡树选手报到~~
此题颜色数极少，显然可以对每种颜色暴力维护
但是写好几颗树很麻烦，我们就可以考虑把颜色压位
然后就得出区间合并的方法，`sum=lc->sum|rc->sum`
为了减少需要加一减一的边界细节，用平衡树来实现区间操作
~~fhqtxdy!~~
一定要注意，区间可能$l>r$，需要判断
真心感觉fhq好写，代码量跟线段树差不多甚至少于线段树
而且维护不同的信息只需要修改`pushdown`和`maintain`就行了
~~常数也可以接受~~
```cpp
#include<cstdio>
#include<cstdlib>
#include<algorithm>
struct Node
{
int val,sum,size,tag,pri;
Node *lc,*rc;
Node(int v):
val(v),
sum(v),
size(1),
tag(0),
pri(rand()),
lc(NULL),
rc(NULL)
{}
void push_down()
{
if(tag==0)return;
val=tag;
sum=tag;
if(lc!=NULL)lc->tag=tag;
if(rc!=NULL)rc->tag=tag;
tag=0;
}
void maintain()
{
size=1;
sum=val;
if(lc!=NULL)
{
lc->push_down();
size+=lc->size;
sum|=lc->sum;
}
if(rc!=NULL)
{
rc->push_down();
size+=rc->size;
sum|=rc->sum;
}
}
};
Node *root;
Node *merge(Node *l,Node *r)
{
if(l==NULL)return r;
if(r==NULL)return l;
if(l->pri<r->pri)
{
l->push_down();
l->rc=merge(l->rc,r);
l->maintain();
return l;
}
else
{
r->push_down();
r->lc=merge(l,r->lc);
r->maintain();
return r;
}
}
void split(Node *rt,int k,Node *&l,Node *&r)
{
if(rt==NULL)
{
l=r=NULL;
return;
}
int s=0;
if(rt->lc!=NULL)s=rt->lc->size;
rt->push_down();
if(s+1<k)
{
l=rt;
split(l->rc,k-s-1,l->rc,r);
}
else
{
r=rt;
split(r->lc,k,l,r->lc);
}
rt->maintain();
}
void paint(int l,int r,int c)
{
Node *p1,*p2,*p3;
split(root,r+1,p2,p3);
split(p2,l,p1,p2);
p2->tag=1<<c;
root=merge(merge(p1,p2),p3);
}
int bit_count(int x)
{
int res=0;
while(x)
{
res+=x&1;
x>>=1;
}
return res;
}
int query(int l,int r)
{
Node *p1,*p2,*p3;
split(root,r+1,p2,p3);
split(p2,l,p1,p2);
p2->push_down();
int res=bit_count(p2->sum);
root=merge(merge(p1,p2),p3);
return res;
}
int n,m;
char readc()
{
char c=getchar();
while(c<'A'||c>'Z')c=getchar();
return c;
}
int main()
{
scanf("%d%*d%d\n",&n,&m);
for(int i=0;i<n;++i)
{
root=merge(root,new Node(2));
}
while(m--)
{
char op;
int l,r,c;
op=readc();
scanf("%d%d",&l,&r);
if(l>r)std::swap(l,r);
if(op=='C')
{
scanf("%d",&c);
paint(l,r,c);
}
if(op=='P')
{
printf("%d\n",query(l,r));
}
}
}
```