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

          这道题大体意思就是，本来是一段无色的区间，然后进行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");
	}
}