学步园

http://poj.org/problem?id=2777

题意：给定一个长为L的棒，它可以分成若干个整数区间。有最多30种颜色，棒上最初的颜色为1，每次操作有'C'和'P'两种：

C A B C 表示给区间[A,B]涂颜色C，

P A B 表示[A,B]区间涂了多少种不同的颜色。

思路：

这个题与poj2528贴海报类似，涂色问题。之前做poj2528时并不知道这个思想，对代码理解的也不透彻。做了这道题以后，对Lazy-Tag思想有了更深的理解了。

当建立好一棵线段树之后，就是往上面涂色。涂色问题可分为以下几个步骤：

1.如果当前区间已经染色，且其颜色和欲染颜色相同，则直接退出（这句可以不要）

2.如果当前区间被欲染色区间完全覆盖，那么当前区间的子区间也被覆盖，那么直接给当前区间染上该颜色直接退出。

3.如果没有被完全覆盖，首先给左右子树染成当前区间的颜色，然后当前区间颜色赋值为混合色为0，再递归染色左右子树。

这样修改被完全覆盖的区间时就可以直接修改而不用遍历左右子树，而对于没有被完全覆盖的区间，先将其颜色传给左右子树，再递归修改，保证了子树颜色的正确性。大大降低了时间复杂度。

对于区间统计，设置mark数组，标记某一颜色是否显现出来。如果一个区间涂上了红色，那么这个区间的任何子区间都涂上了红色，mark标记为1，就不必向下遍历了。当是混合色（为0时）就要继续遍历子树。最后统计mark值为1的个数即可。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int maxn = 100005;

struct line
{
	int l;
	int r;
	int kind;
}tree[4*maxn];

bool mark[35];

void build(int v,int l, int r)
{
	tree[v].l = l;
	tree[v].r = r;
	tree[v].kind = 1;
	if(l == r)
		return;
	int mid = (l+r)>>1;
	build(v*2,l,mid);
	build(v*2+1,mid+1,r);
}

void update(int v, int l, int r, int cover)
{
	if(tree[v].l == l && tree[v].r == r)
	{
		tree[v].kind = cover;
		return;
	}

	if(tree[v].kind != 0 && tree[v].kind != cover)
	{
		tree[v*2].kind = tree[v].kind;	//向下传递
		tree[v*2+1].kind = tree[v].kind;
		tree[v].kind = 0;
	}

	int mid = (tree[v].l+tree[v].r)>>1;
	if(r <= mid)
		update(v*2,l,r,cover);
	else if(l > mid)
		update(v*2+1,l,r,cover);
	else
	{
		update(v*2,l,mid,cover);
		update(v*2+1,mid+1,r,cover);
	}
}

void query(int v, int l, int r)
{
	if(tree[v].kind > 0)
	{
		mark[tree[v].kind] = true;	//该区间被染了纯色，标记直接退出，因为它子区间也肯定是纯色
		return;
	}

	int mid = (tree[v].l+tree[v].r)>>1;
	if(r <= mid)
		query(v*2,l,r);
	else if(l > mid)
		query(v*2+1,l,r);
	else
	{
		query(v*2,l,mid);
		query(v*2+1,mid+1,r);
	}
}

int main()
{
	int n,color,m;
	scanf("%d %d %d",&n,&color,&m);

	build(1,1,n);

	char ch[2];
	int a,b,c;
	while(m--)
	{
		scanf("%s",ch);
		if(ch[0] == 'C')
		{
			scanf("%d %d %d",&a,&b,&c);
			if(a > b)
				std::swap(a,b);
			update(1,a,b,c);
		}
		else
		{
			scanf("%d %d",&a,&b);
			if(a > b)
				std::swap(a,b);
			memset(mark,false,sizeof(mark));

			query(1,a,b);
			int ans = 0;
			for(int i = 1; i <= color; i++)	//统计
			{
				if(mark[i])	
					ans += 1;
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}