count the colors(zoj涂色线段数，线段树).cpp

杭电acm解题报告2001---2099.

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

struct node {
	int l,r;
	node * pl, * pr;
	int col;//-1无色，-2混合色，>=0单一色
	int lbd,rbd;
}mem[20000];
int mem_pos, n;
int seg[8100];

node *
new_node()
{
	node * pt = &mem[mem_pos ++];
	memset(pt,0,sizeof(node));
	return pt;
}

node *
make_tree(int il, int ir)
{
	node * root = new_node();
	root ->l = il;
	root ->r = ir;
	if(ir - il > 1) {
		int mid = (il+ir)/2;
		root ->pl = make_tree(il, mid);
		root ->pr = make_tree(mid, ir);
	}
	return root;
}

void color(node * root, int c)
{
	root ->col = c;
	root ->lbd = root ->rbd = c;
}

void
update(node * root, int x, int y, int c)
{
	if(root ->l == x && root ->r == y) {
		color(root, c);
		return ;
	}
	if(root ->col >= 0) {
		color(root ->pl, root ->col);
		color(root ->pr, root ->col);
	}
	root ->col = -2;

	if(root ->pl ->r > x) {
		if(root ->pl ->r >= y) {
			update(root ->pl, x,y,c);
		}
		else {
			int mid = (root ->l + root ->r)/2;
			update(root ->pl, x,mid, c);
			update(root ->pr, mid,y, c);
		}
	}
	else {
		update(root ->pr, x,y, c);
	}

	root ->lbd = root ->pl ->lbd;
	root ->rbd = root ->pr ->rbd;
}

void
search(node * root, int x,int y)
{
	if(root ->col >= 0) {
		seg[ root ->col ] ++;
		return ;
	}
	if(root ->r - root ->l <= 1 || root ->col == -1) {
		return ;
	}

	if(root ->pl ->r > x) {
		if(root ->pl ->r >= y) {
			search(root ->pl, x,y);
		}
		else {
			int mid = (root ->l + root ->r)/2;
			search(root ->pl, x,mid);
			search(root ->pr, mid,y);
		}
	}
	else {
		search(root ->pr, x,y);
	}

	if(root ->pr ->lbd != -1 && root ->pl ->rbd != -1) {
		if(root ->pr ->lbd == root ->pl ->rbd) {
			seg[ root ->pl ->rbd ] --;
		}
	}
}

int main()
{
	int i,cx,cy;
	mem_pos = 0;
	node * root = make_tree(0,8000);
	while(scanf("%d", &n)==1) {
		for(i=0;i<mem_pos;i++) {
			mem[i].col = mem[i].lbd = mem[i].rbd = -1;
		}
		cy = INT_MIN;
		for(i=0;i<n;i++) {
			int x,y,c;
			scanf("%d %d %d", &x,&y,&c);
			update(root,x,y,c);
			cy = max(cy, c);
		}
		memset(seg,0,sizeof(seg));
		search(root,0,8000);
		for(i=0;i<=cy;i++) {
			if(seg[i] != 0) {
				printf("%d %d\n", i,seg[i]);
			}
		}
		printf("\n");
	}
}