POJ2777 线段树染色

题意：

初始颜色均为1，俩操作

修改：将【l,r】染为颜色Z

查询：【l,r】的不同颜色数

1e5个点，1e5个操作，30种颜色

思路：

查询：如果查询维护区间颜色数，不满足区间加法

颜色数较少，维护区间颜色状态S (val)

pushup：当前子树S=左子树S |  右子树S

修改：维护颜色替换标记lazy

注意pushdown跟update中的对lazy跟val的写法

难度：0.8

391ms

#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
const int inf=0x3f3f3f;
struct Stree
{
	int val;//二进制表示存的颜色状态
	int lazy;
} sts[4*100005]; //开4倍

int pushup(int root)
{
	sts[root].val=sts[root<<1].val|sts[root<<1|1].val;
}
int pushdown(int root)
{
	if(sts[root].lazy!=0)
	{
		sts[root<<1].lazy=sts[root].lazy;
		sts[root<<1|1].lazy=sts[root].lazy;
		sts[root<<1].val=sts[root].lazy;//注意：这里的lazy已经移位了。 无需再次移位 
		sts[root<<1|1].val=sts[root].lazy;//同上 
		sts[root].lazy=0;
	}
}
void build(int l,int r,int root)//根节点从1开始吧
{
	if(l==r)//到达子节点
	{
		sts[root].val=1;
		sts[root].lazy=0;
	}
	else
	{
		sts[root].val=sts[root].lazy=0;//没了这句会WA，清空lazy跟val
		int mid=(l+r)>>1;//(l+r)/2
		build(l,mid,root<<1);
		build(mid+1,r,root<<1|1);
		pushup(root);//更新本节点
	}
}
int query(int nowl,int nowr,int ql,int qr,int root)
{
	if(nowl>=ql&&nowr<=qr)
	{
		return sts[root].val;
	}
	pushdown(root);
	int mid=(nowl+nowr)>>1;
	int ans=0;
	if(ql<=mid)ans|=query(nowl,mid,ql,qr,root<<1);
	if(qr>mid)ans|=query(mid+1,nowr,ql,qr,root<<1|1);
	return ans;
}

void update(int nowl,int nowr,int ul,int ur,int root,int addval)//nowl,nowr 当前区间  ul,ur 需修改的区间
{
	if(ul<=nowl&&ur>=nowr)//当前区间是修改区间的子区间
	{
		sts[root].val=(1<<(addval-1));
		sts[root].lazy=(1<<(addval-1));
		return ;
	}
	int mid=(nowl+nowr)>>1;
	pushdown(root);
	if(ul<=mid) update(nowl,mid,ul,ur,root<<1,addval);//左子树与修改区间有交集
	if(ur>mid)  update(mid+1,nowr,ul,ur,root<<1|1,addval);
	pushup(root);

}
void op(int n);
int main()
{

	int ll,tt,oo;
	while(cin>>ll>>tt>>oo)
	{
		build(1,ll,1);
		//op(ll);
		getchar();
		int l,r,change;char c;//写成 int c 卡了半天 
		for(int i=1; i<=oo; i++)
		{
			scanf("%c",&c);
			if(c=='C')
			{
				scanf("%d %d %d",&l,&r,&change);
				if(l>r)swap(l,r);
				update(1,ll,l,r,1,change);
				//op(ll);
			}
			else
			{
				scanf("%d %d",&l,&r);
				if(l>r)swap(l,r);
				int state=query(1,ll,l,r,1);

				int ans=0;
				for(int i=1; i<=tt; i++)
				{
					//printf("state:%d ",state);
					if((state&1)==1)
					{
						ans++;
					}
					state=(state>>1);
				}
				printf("%d\n",ans);
			}

			getchar();
		}
	}


}



void op(int n)
{
	printf("\n///\n");
	int up=pow(2.0,ceil(log10((double)n)/log10(2.0))+1)-1;
	for(int i=1; i<=up; i++)
	{
		printf("%d ",sts[i].val);
		int t=log10((double)i+1.0)/log10(2.0);
		if(pow(2.0,t)==i+1)
			printf("\n");
	}
	printf("///\n");
}