Count Color poj2777 线段树

题意

有一个长木板，现在往上面在一定区间内刷颜色，后来刷的颜色会掩盖掉前面刷的颜色，问每次一定区间内可以看到多少种颜色。

解题思路

这里使用线段树，因为刷颜色可以看作是区间修改，使用lazy标记区间的颜色种类，下传标记后，当前节点的lazy标记就标记为0，然后使用vis数组来标记颜色（颜色种类很少）。剩下的基本就是线段树的模板了。

代码实现

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const int maxn=1e5+17;

struct node{

	int l, r, lazy;

}a[maxn<<2];

int vis[35];//颜色种类

int L, T, O, ans;

void build(int rt, int l, int r)

{

	a[rt].l=l;

	a[rt].r=r;

	a[rt].lazy=1;//默认为第一种颜色

	if(l==r){

		return ;

	}

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

	build(rt<<1, l, mid);

	build(rt<<1|1, mid+1, r);

}

void down(int k)

{

	a[k<<1].lazy=a[k].lazy;

	a[k<<1|1].lazy=a[k].lazy;

	a[k].lazy=0;//表示他的节点下面可能是两种不同的颜色

}

void update(int rt, int L, int R, int x)

{

	if(L<=a[rt].l && a[rt].r<=R)

	{

		a[rt].lazy=x;

		return ;

	}

	int mid=(a[rt].l+a[rt].r)>>1;

	if(a[rt].lazy !=0 ) //记得一定要下传标记

		down(rt);

	if(L<=mid) update(rt<<1, L, R, x);

	if(R>mid) update(rt<<1|1, L, R, x);

}

void query(int rt, int L, int R)

{

	if(a[rt].lazy!=0) //如果不为零就可以进行判断，因为下面的也是这种颜色

	{

		if(!vis[a[rt].lazy])// 看是否之前标记过

		{

			ans++; //没有标记就加一

			vis[a[rt].lazy]=1; //标记

		}

		return ;

	}

	int mid=(a[rt].l+a[rt].r)>>1;

	if(a[rt].lazy!=0)

		down(rt);

	if(L<=mid) query(rt<<1, L, R);

	if(R>mid) query(rt<<1|1, L, R);

}

int main()

{

	int l, r, c;

	char s[4];

	while(scanf("%d%d%d", &L, &T, &O)!=EOF)

	{

		build(1, 1, L);

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

		{

			scanf("%s", s);

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

			{

				scanf("%d%d%d", &l, &r, &c);

				if(l > r){

					swap(l, r);

				}

				update(1, l, r, c);

			}

			else {

				scanf("%d%d", &l, &r);

				if(l > r) {

					swap(l, r);

				}

				memset(vis, 0, sizeof(vis));

				ans=0;

				query(1, l, r);

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

			}

		}

	}

	return 0;

}

巴特西

Count Color poj2777 线段树

Count Color poj2777 线段树

题意

解题思路

代码实现

最新文章

热门文章