ZOJ1610 线段树区间计数

（这题和之前的某道区间建立正好相反，给整懵了。）
题意： 给定一个长为 8000 8000 8000的区间，每次染色一定长度的区间，最后问你每种颜色的区间有多少段。
题解： 注意必须建 8000 8000 8000的树，然后模拟下递归过程（蒟蒻只会这么推）改下查询操作。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 8010;
struct Node{
	int l, r, c;
}tr[N << 2];
int n, now, num[N];

void pushdown(int u) {
	if(tr[u].c != -1) {
		tr[u << 1].c = tr[u << 1 | 1].c = tr[u].c;
		tr[u].c = -1;
	}
}

void build(int u, int l, int r) {
	tr[u] = {l, r, -1};
	if(l == r) return ;
	
	int mid = l + r >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

void modify(int u, int l, int r, int c) {
	if(tr[u].l == l && tr[u].r == r) {
		tr[u].c = c;
		return ;
	}
	
	pushdown(u);
	int mid = tr[u].l + tr[u].r >> 1;
	if(r <= mid) modify(u << 1, l, r, c);
	else if(l > mid) modify(u << 1 | 1, l, r, c);
	else modify(u << 1, l, mid, c), modify(u << 1 | 1, mid + 1, r, c);
}

void query(int u) {
	if(tr[u].c != -1) {
		if(tr[u].c != now) num[tr[u].c]++;
		now = tr[u].c;
		return ;
	}
	
	if(tr[u].l == tr[u].r) {
		now = -1;
		return ;
	}
	query(u << 1);
	query(u << 1 | 1);
}

int main()
{
	while(~scanf("%d", &n)) {
		now = -1;
		memset(num, 0, sizeof num);
		build(1, 1, 8000);
	
		for(int i = 1; i <= n; i++) {
			int a, b, c;
			scanf("%d%d%d", &a, &b, &c);
			if(a < b) modify(1, a + 1, b, c);
		}
		
		query(1);
		for(int i = 0; i <= 8000; i++)
			if(num[i]) printf("%d %d\n", i, num[i]);
		puts(""); 
	}
	
	return 0;
}