洛谷 P1558 色板游戏（线段树）

题目传送门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";
		}
	}
}