poj 2777 Count Color(線段樹 Lazy-Tag思想 成段更新+區間統計)

題意：給定一個長為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 
#include 
#include 
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
,ans);
		}
	}
	return 0;
}