题目传送门
https://www.luogu.com.cn/problem/P1558跳到了一道线段树模板题……
解题思路
主要就 2 个操作：
1. 修改区间；2. 区间查询。
很容易可以想到线段树。
同时，观察到：颜色的数量 ，于是想到了状态压缩。
于是，线段树的每个节点都会有 ，
为它管辖的区间，
为它区间内的各个颜色的状态压缩，
为懒标记（也是状态压缩的）。
区间修改的话就是线段树的模板；
但是，区间查询，我们需要注意重复的颜色不要算重了即可。
总的来说，就是差不多一道线段树的模板题……
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,q;
int c;
struct tree{int l,r,sum,zt,add;
}tr[400001];
void build(int u,int l,int r)
{tr[u]={l,r,0,1,1};if(l==r)return;int mid=l+r>>1;build(u*2,l,mid);build(u*2+1,mid+1,r);
}
void push_down(int u)
{if(tr[u].add){//if(tr[u*2].zt&tr[u].add==0)// tr[u*2].sum++;tr[u*2].zt=tr[u].add;tr[u*2].add=tr[u].add;//if(tr[u*2+1].zt&tr[u].add==0)// tr[u*2+1].sum++;tr[u*2+1].zt=tr[u].add;tr[u*2+1].add=tr[u].add;tr[u].add=0;}
}
void change(int u,int l,int r,int d)
{if(l<=tr[u].l&&tr[u].r<=r){//if(d&tr[u].zt==0)tr[u].sum++;tr[u].zt=d;tr[u].add=d;return;}push_down(u);int mid=tr[u].l+tr[u].r>>1;if(l<=mid)change(u*2,l,r,d);if(r>mid)change(u*2+1,l,r,d);tr[u].zt=tr[u*2].zt|tr[u*2+1].zt;
}
int count(int x)
{int res=0;while(x){if(x&1)res++;x>>=1;}return res;
}
int query(int u,int l,int r)
{
// cout<<tr[u].l<<" "<<tr[u].r<<endl;if(l<=tr[u].l&&tr[u].r<=r){return tr[u].zt;}push_down(u);int mid=tr[u].l+tr[u].r>>1;int res=0;if(l<=mid)res|=query(u*2,l,r);if(r>mid)res|=query(u*2+1,l,r);return res;
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m>>q;build(1,1,n);char ch;int x,y,z;while(q--){cin>>ch;if(ch=='C'){cin>>x>>y>>z;if(x>y)swap(x,y);change(1,x,y,1<<(z-1));}else{c=0;cin>>x>>y;if(x>y)swap(x,y);cout<<count(query(1,x,y))<<"\n";}}
}