hdu - 5023 - A Corrupt Mayor's Performance Art（线段树）

题意：一长由N小段组成的长条，每小段的初始颜色为2。现执行M个操作，每个操作是以下两种中的一种(0 < N <= 1,000,000; 0<M<=100,000) ：

P a b c ——> 将段a到段b涂成颜色c，c是1, 2, ... 30中的一种(0 < a<=b <= N, 0 < c <= 30)。

Q a b ——> 问段a到段b之间有哪几种颜色，按颜色大小从小到大输出(0 < a<=b <= N, 0 < c <= 30)。

——>>很明显此题可以用线段树实现Mlog(N)的解法。。（看完输入就敲题了，把初始颜色设为了无，耗了好多时间：看题要仔细啊。。）

#include <cstdio>
#include <set>

#define lc (o << 1)
#define rc ((o << 1) | 1)

using std::set;

const int MAXN = 1000000 + 10;

int g_nColor[MAXN << 2];
set<int> g_sRet;

void Initialize()
{
	g_sRet.clear();
}

void Build(int o, int L, int R)
{
	g_nColor[o] = 2;
	if (L == R)
	{
		return;
	}
	int M = (L + R) >> 1;
	Build(lc, L, M);
	Build(rc, M + 1, R);
}

void Pushdown(int o)
{
	if (g_nColor[o])
	{
		g_nColor[lc] = g_nColor[rc] = g_nColor[o];
		g_nColor[o] = 0;
	}
}

void Update(int o, int L, int R, int ql, int qr, int nColor)
{
	if (ql <= L && R <= qr)
	{
		g_nColor[o] = nColor;
		return;
	}
	Pushdown(o);
	int M = (L + R) >> 1;
	if (ql <= M)
	{
		Update(lc, L, M, ql, qr, nColor);
	}
	if (qr > M)
	{
		Update(rc, M + 1, R, ql, qr, nColor);
	}
}

void Query(int o, int L, int R, int ql, int qr)
{
	if (ql <= L && R <= qr && g_nColor[o])
	{
		g_sRet.insert(g_nColor[o]);
		return;
	}
	if (L == R)
	{
		return;
	}
	Pushdown(o);
	int M = (L + R) >> 1;
	if (ql <= M)
	{
		Query(lc, L, M, ql, qr);
	}
	if (qr > M)
	{
		Query(rc, M + 1, R, ql, qr);
	}
}

void Output()
{
	if (g_sRet.empty())
	{
		return;
	}
	set<int>::const_iterator iter = g_sRet.begin();
	size_t nCnt = 0;
	for (; nCnt < g_sRet.size() - 1; ++nCnt, ++iter)
	{
		printf("%d ", *iter);
	}
	printf("%d\n", *iter);
}

int main()
{
	int N, M, a, b, c;
	char chOperation;

	while (scanf("%d%d", &N, &M) == 2 && (N && M))
	{
		Build(1, 1, N);
		while (M--)
		{
			getchar();
			chOperation = getchar();
			if (chOperation == 'P')
			{
				scanf("%d%d%d", &a, &b, &c);
				Update(1, 1, N, a, b, c);
			}
			else
			{
				scanf("%d%d", &a, &b);
				Initialize();
				Query(1, 1, N, a, b);
				Output();
			}
		}
	}

	return 0;
}

hdu - 5023 - A Corrupt Mayor's Performance Art（线段树）

原文：http://blog.csdn.net/scnu_jiechao/article/details/39449681