【POJ 2777】 Count Color（线段树区间更新与查询）

Description

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

Source

感觉有些神经衰弱了。。。写发水水的线段树放松放松。。。

一直在搞图论 是该换换弦 磨得快锈了 太折磨人了……（弱也不知道说了些啥

一块木板 长L(1~L) 有T种颜色的油漆标号1~T 默认木板初始是1号颜色

进行O次操作 操作有两种

C a b c 表示木板a~b段涂c种油漆（若之前涂过其它颜色 则覆盖掉）

P a b 表示询问木板a~b段如今涂了几种油漆

两个数组 一个存树 一个存涂了哪几种油漆

存树的表示a~b涂的某种颜色 然后搞搞就出来了……好乏

代码例如以下：

#include <iostream>

#include <cmath>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <cstring>

#include <queue>

#include <stack>

#include <list>

#include <algorithm>

#include <map>

#include <set>

#define LL long long

#define Pr pair<int,int>

#define fread() freopen("in.in","r",stdin)

#define fwrite() freopen("out.out","w",stdout)

using namespace std;

const int INF = 0x3f3f3f3f;

const int msz = 10000;

const int mod = 1e9+7;

const double eps = 1e-8;

int tr[400400];

bool col[33];

int L,T,O;

void Color(int root,int l,int r,int a,int b,int c)

{

	if(a == l && b == r)

	{

		tr[root] = c;

		return;

	}

	int mid = (l+r)>>1;

	if(tr[root])

		tr[root<<1] = tr[root<<1|1] = tr[root];

	tr[root] = 0;

	if(mid >= b) Color(root<<1,l,mid,a,b,c);

	else if(mid+1 <= a) Color(root<<1|1,mid+1,r,a,b,c);

	else

	{

		Color(root<<1,l,mid,a,mid,c);

		Color(root<<1|1,mid+1,r,mid+1,b,c);

	}

}

void Search(int root,int l,int r,int a,int b)

{

	//printf("root:%d l:%d r:%d co:%d\n",root,l,r,tr[root]);

	if(tr[root])

	{

		col[tr[root]] = 1;

		return;

	}

	int mid = (l+r)>>1;

	if(mid >= b) Search(root<<1,l,mid,a,b);

	else if(mid+1 <= a) Search(root<<1|1,mid+1,r,a,b);

	else

	{

		Search(root<<1,l,mid,a,mid);

		Search(root<<1|1,mid+1,r,mid+1,b);

	}

}

int main()

{

	//fread();

	//fwrite();

	char opt[3];

	int a,b,c;

	while(~scanf("%d%d%d",&L,&T,&O))

	{

		memset(tr,0,sizeof(tr));

		tr[1] = 1;

		while(O--)

		{

			scanf("%s",opt);

			scanf("%d%d",&a,&b);

			if(a > b) swap(a,b);

			if(opt[0] == 'C')

			{

				scanf("%d",&c);

				Color(1,1,L,a,b,c);

			}

			else

			{

				memset(col,0,sizeof(col));

				Search(1,1,L,a,b);

				int ans = 0;

				for(int i = 1; i <= T; ++i)

					ans += col[i];

				printf("%d\n",ans);

			}

		}

	}

	return 0;

}