题意:给一个固定长度为L的画板。有两个操作:1、C A B C:区间AB内涂上颜色C。2、P A B:查询区间AB内颜色种类数。
思路:区间显然要用线段树。颜色因为不超过30,所以可以用位运算。关键在于优化:每次更新到完整区间的时候标记一下,不更新到叶子节点,当后面更新或者查询需要用到比这个区间小的区间的时候再往下带。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100005
struct node{
int l,r,c;
bool flag;//表示该区间的颜色是否更新到了叶子节点
}t[N<<2];
int n,num,q;
int mid(int a,int b){
return (a+b)>>1;
}
void createTree(int root,int l,int r){
t[root].l = l;
t[root].r = r;
t[root].flag = false;
t[root].c = 1;
if(l!=r){
createTree(root*2, l, mid(l,r));
createTree(root*2+1, mid(l,r)+1, r);
}
}
void push(int root){
t[root].flag = false;
t[root*2].flag = t[root*2+1].flag = true;
t[root*2].c = t[root*2+1].c = t[root].c;
}
void update(int root,int a,int b,int x){
int mm = mid(t[root].l,t[root].r);
if(t[root].l == a && t[root].r == b){//更新时候如果是整个区间那么标记,不再往下更新
t[root].c = (1<<x);
t[root].flag = true;
return ;
}
if(t[root].flag)//如果需要,再往下带更新操作
push(root);
if(b <= mm)
update(root*2,a,b,x);
else if(a>mm)
update(root*2+1, a, b, x);
else{
update(root*2, a, mm, x);
update(root*2+1, mm+1, b, x);
}
t[root].c = t[root*2].c | t[root*2+1].c;
}
int query(int root,int a,int b){
int mm = mid(t[root].l,t[root].r);
if(t[root].l == a && t[root].r == b)
return t[root].c;
if(t[root].flag)
push(root);
if(b <= mm)
return query(root*2, a, b);
else if(a > mm)
return query(root*2+1, a, b);
else
return query(root*2, a, mm) | query(root*2+1, mm+1, b);
}
int main(){
int i,a,b,x,res;
char cmd[5];
scanf("%d %d %d",&n,&num,&q);
createTree(1,1,n);
while(q--){
scanf("%s %d %d",cmd,&a,&b);
if(a>b)
swap(a,b);
if(cmd[0] == 'C'){
scanf("%d",&x);
update(1,a,b,x-1);
}else{
res=0;
x = query(1,a,b);
for(i = 0;i<num;i++)
if(x & (1<<i))
res++;
printf("%d\n",res);
}
}
return 0;
}
因篇幅问题不能全部显示,请点此查看更多更全内容
怀疑对方AI换脸可以让对方摁鼻子 真人摁下去鼻子会变形
女子野生动物园下车狼悄悄靠近 后车司机按喇叭提醒
睡前玩8分钟手机身体兴奋1小时 还可能让你“变丑”
惊蛰为啥吃梨?倒春寒来不来就看惊蛰
男子高速犯困开智能驾驶出事故 60万刚买的奔驰严重损毁