POJ2777（线段树区间更新+LAZY）

涂色问题，题意我就不说了。

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#define LL long long
#define maxn 200005
using namespace std;

struct Node
{
	int color;
	int left,right;
};
struct Node node[maxn*4];
int vis[31];

void build(int o,int L,int R)					//建树
{
	node[o].color=1;							//初始为1
	node[o].left=L;
	node[o].right=R;
	if(node[o].left==node[o].right)
		return;
	int M=(L+R)>>1;
	build(o<<1,L,M);
	build(o<<1|1,M+1,R);
}

void pushdown(int o)							//LAZY操作
{
	if(node[o].color>0)
	{
		node[o<<1].color=node[o<<1|1].color=node[o].color;
		node[o].color=-1;
	}
}

void update(int o,int L,int R,int c)			//更新
{
	if(L<=node[o].left && R>=node[o].right)
	{
		node[o].color=c;						//上色
		return;
	}
	pushdown(o);
	int M=(node[o].left+node[o].right)>>1;
	if(R<=M)									//左子树
		update(o*2,L,R,c);
	else
	{
		if(L>M)									//右子树
			update(o*2+1,L,R,c);
		else									//左右子树都有的情况
		{
			update(o*2,L,M,c);
			update(o*2+1,M+1,R,c);
		}
	}
}

void query(int o,int L,int R)
{
	if(node[o].color>0)
	{
		vis[node[o].color]=1;					//1表示这种颜色能看到，0表示不能
		return;
	}
	if(node[o].left==node[o].right)
		return;
	int M=(node[o].left+node[o].right)>>1;
	if(R<=M)
		query(o*2,L,R);
	else
	{
		if(L>M)
			query(o*2+1,L,R);
		else
		{
			query(o*2,L,M);
			query(o*2+1,M+1,R);
		}
	}
}

int Getans(int t)
{
	int ans=0;
	for(int i=1;i<=t;i++)
		if(vis[i]==1)
			ans++;
	return ans;
}

int main()
{
	int len,t,o;
	scanf("%d%d%d",&len,&t,&o);
	build(1,1,len);
	while(o--)
	{
		char ch;
		getchar();
		scanf("%c",&ch);
		if(ch==‘C‘)
		{
			int ll,rr,c;
			scanf("%d%d%d",&ll,&rr,&c);
			if(ll>rr)								//注意ll可能是大于rr的。题目中有说
				update(1,rr,ll,c);
			else
				update(1,ll,rr,c);
		}
		else
		{
			int ll,rr;
			memset(vis,0,sizeof(vis));
			scanf("%d%d",&ll,&rr);
			if(ll>rr)
				query(1,rr,ll);
			else
				query(1,ll,rr);
			printf("%d\n",Getans(t));
		}
	}
	return 0;
}

POJ2777（线段树区间更新+LAZY）,布布扣,bubuko.com

POJ2777（线段树区间更新+LAZY）

原文：http://blog.csdn.net/mfmy_szw/article/details/21277467