Rockdu's Blog

Input

Output

Sample Input

2 2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2​

Sample Output

2
1​​

区间覆盖问题首先可以想到线段树。但是如果直接按有多少种颜色作为节点键值的话很快就会发现是无法从儿子获得信息的。考虑到颜色只有30种，我们可以用一个二进制数的2^i为1来表示有i这种颜色，最后查询时返回记载哪些颜色出现过的二进制数，然后数有多少位为1即可。

之所以贴这道题是因为它与DP类似的核心的思想——把直接获得答案转换为表示某个答案或查找某个答案可不可行。间接地使得信息可以向上一层传递。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100007;

struct node
{
	int l,r;
	int color;//状态压缩 
	int covered; 
}tree[maxn*4];

void build_tree(int l,int r,int rt)
{
	tree[rt].l=l;tree[rt].r=r;
	tree[rt].color=1;
	tree[rt].covered=1;
	if(l==r)	return;
	int m=(l+r)/2;
	build_tree(l,m,rt*2);
	build_tree(m+1,r,rt*2+1);
}

void pushup(int rt)
{
	tree[rt].color=tree[rt*2].color | tree[rt*2+1].color;
}

void pushdown(int rt)
{
	if(tree[rt].covered)
	{
		tree[rt*2].color=tree[rt].color;
		tree[rt*2].covered=1;
		tree[rt*2+1].color=tree[rt].color;
		tree[rt*2+1].covered=1;
		tree[rt].covered=0;
	}
}

void update(int l,int r,int clr,int rt)/*处理过的颜色*/
{
	int tl=tree[rt].l,tr=tree[rt].r;
	if(l==tl && r==tr)
	{
		tree[rt].color=clr; //赋值 
		tree[rt].covered=1;
		return; 
	}
	pushdown(rt);
	int m=(tl+tr)/2;
	if(r<=m)	update(l,r,clr,rt*2);
	else if(l>m)	update(l,r,clr,rt*2+1);
	else{
		update(l,m,clr,rt*2);
		update(m+1,r,clr,rt*2+1);
	}
	pushup(rt);
}

int query(int l,int r,int rt)
{
	int tl=tree[rt].l,tr=tree[rt].r;
	if(tl==l && tr==r)
		return tree[rt].color;
	if(tree[rt].covered)
		return tree[rt].color;
	int m=(tl+tr)/2;
	if(r<=m)	return query(l,r,rt*2);
	else if(l>m)	return query(l,r,rt*2+1);
	else{
		int p1,p2;
		p1=query(l,m,rt*2);
		p2=query(m+1,r,rt*2+1);
		return p1 | p2;
	}
}

int cnt(int num)
{
	int ans=0;
	while(num!=0)
	{
		if(num&1)	
			ans++;
		num=num>>1;
	}
	return ans;
}

int main()
{
	int t,l,o;
	scanf("%d%d%d",&l,&t,&o);
	char c;
	build_tree(1,l,1);
	for(int i=1;i<=o;i++)
	{
		scanf(" %c",&c);
		if(c=='C')
			{
				int l,r,clr;
				scanf("%d%d%d",&l,&r,&clr);
				if(l>r) swap(l,r);
				update(l,r,1<<(clr-1),1);
			}
		else
			{
				int l,r;
				scanf("%d%d",&l,&r);
				if(l>r) swap(l,r);
				printf("%d\n",cnt(query(l,r,1)));
			}
	}
	return 0;
}