ZOJ - 1610 Count the Colors（以区间为”点“的线段树）

Count the Colors

Time Limit: 2 Seconds Memory Limit: 65536 KB

Painting some colored segments on a line, some previously painted segments may be covered by some the subsequent ones.

Your task is counting the segments of different colors you can see at last.

Input

The first line of each data set contains exactly one integer n, 1 <= n <= 8000, equal to the number of colored segments.

Each of the following n lines consists of exactly 3 nonnegative integers separated by single spaces:

x1 x2 c

x1 and x2 indicate the left endpoint and right endpoint of the segment, c indicates the color of the segment.

All the numbers are in the range [0, 8000], and they are all integers.

Input may contain several data set, process to the end of file.

Output

Each line of the output should contain a color index that can be seen from the top, following the count of the segments of this color, they should be printed according to the color index.

If some color can't be seen, you shouldn't print it.

Print a blank line after every dataset.

Sample Input

5
0 4 4
0 3 1
3 4 2
0 2 2
0 2 3
4
0 1 1
3 4 1
1 3 2
1 3 1
6
0 1 0
1 2 1
2 3 1
1 2 0
2 3 0
1 2 1

Sample Output

1 1
2 1
3 1

1 1

0 2
1 1

这道题大体意思就是，本来是一段无色的区间，然后进行n步操作来进行染色，在最后的时候分别输出以各种颜色为基准的区间数量有多少。

这道题最重要的一点就是这是区间的染色！！不能和平常的点集的建树和改变一样操作。我仿照kuangbin大佬的模板写了一遍，顺便记录心得~~在代码中给出；

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 8010;
struct ***
{
	int l, r, col;
}tr[maxn<<2];//所建之树
int color[maxn];//每种颜色的区间数量
int temp;//用来判断区间前后的颜色是否连续
void build(int rt, int l, int r)
{
	tr[rt].l = l;
	tr[rt].r = r;
	tr[rt].col = -1;
	if (l + 1 == r)//不能出现点的请况
	{
		return;
	}
	int mid = ((l + r) >> 1);
	build(rt << 1, l, mid);
	build(rt << 1 | 1, mid, r);//这里不同的是；两个都是mid，从而达到了题目中所需的把区间作为点的实现；
}
void insert(int rt, int l, int r, int c)
{
	if (l == r)return;//点的情况
	if (tr[rt].col == c)return;//如果本来颜色相同，就不用继续了
	if (l <= tr[rt].l&&r >= tr[rt].r)//如果这段区间被包含，直接区间的改颜色就好
	{
		tr[rt].col = c;
		return;
	}
	if (tr[rt].col >= 0)//如果已经被染色过
	{
		tr[rt << 1 | 1].col = tr[rt << 1].col = tr[rt].col;//之前的颜色传下去
		tr[rt].col = -2;//标记这是存在混合颜色的情况
	}
	int mid = ((tr[rt].l + tr[rt].r) >> 1);
	if (r <= mid)//开始分情况进行染色
	{
		insert(rt << 1, l, r, c);
	}
	else if (l >= mid)
	{
		insert(rt << 1 | 1, l, r, c);
	}
	else
	{
		insert(rt << 1, l, mid, c);
		insert(rt << 1 | 1, mid, r, c);
	}
	tr[rt].col = -2;
}
void count(int s)//开始数数量
{
	if (tr[s].col == -1)
	{
		temp = -1;
		return;
	}
	if (tr[s].col != -2)//只有一个颜色
	{
		if (tr[s].col != temp)//是否与之区间区间颜色相同
		{
			color[tr[s].col]++;
			temp = tr[s].col;
		}
		return;
	}
	if (tr[s].l + 1 != tr[s].r)//存在2个以上的单位区间才进行下部操作，防止访问点；
	{
		count(s << 1);
		count(s << 1 | 1);
	}
}
int main()
{
	int n, a, b, c;
	int Max;
	while (scanf("%d", &n) != EOF)
	{
		build(1, 0, 8000);//建树
		Max = 0;//记录最大的颜色标号
		while (n--)
		{
			scanf("%d%d%d", &a, &b, &c);
			insert(1, a, b, c);
			if (c > Max)
			{
				Max = c;
			}
		}
	//	cout << Max << endl;
		temp = -1;
		memset(color, 0, sizeof(color));
		count(1);//开始计数
		for (int s = 0; s <= Max; s++)
		{
			if (color[s])printf("%d %d\n", s, color[s]);//输出；
		}
		printf("\n");
	}
}