ZOJ1610 (C++)

zoj1610.cpp

#include <iostream>
#include <limits.h>
#include <string.h>

using namespace std;

const int maxn=8000,no_color=-1,multi_color=-2;

int flags[maxn];

class segtree {
	private:
		int left,right,color;
		segtree *lson,*rson;
	public:
		segtree(int p, int q) {
			left=p;
			right=q;
			color=no_color;
			lson=NULL;
			rson=NULL;
			if (q-p==1) return;
			int m=(p+q)>>1;
			lson=new segtree(p,m);
			rson=new segtree(m,q);
		}
		void insert(int p, int q, int c);
		void count(int &lc, int &rc);
};

inline int min(int p, int q) {
	return p<q?p:q;
}

inline int max(int p, int q) {
	return p>q?p:q;
}

int main() {
	int n;
	while (cin>>n) {
		int x[maxn]={0},y[maxn]={0},c[maxn]={0};
		int tmpl=INT_MAX,tmpr=-1,tmpc=-1;
		for (int i=0; i<n; i++) {
			cin>>x[i]>>y[i]>>c[i];
			tmpl=min(tmpl,x[i]);
			tmpr=max(tmpr,y[i]);
			tmpc=max(tmpc,c[i]);
		}
		segtree *root=new segtree(tmpl,tmpr);
		for (int i=0; i<n; i++) root->insert(x[i],y[i],c[i]);
		memset(flags,0,sizeof(flags));
		int lc=no_color,rc=no_color;
		root->count(lc,rc);
		for (int i=0; i<=tmpc; i++) 
			if (flags[i]) cout<<i<<" "<<flags[i]<<endl;
		delete root;
		cout<<endl;
	}
	return 0;
}

void segtree::insert(int p, int q, int c) {
	if (p==left && q==right) {
		color=c;
		return;
	}
	if (color==c) return;
	if (right-left==1) return;
	if (color!=multi_color) {
		lson->color=this->color;
		rson->color=this->color;
		this->color=multi_color;
	}
	int m=(left+right)>>1;
	if (q<=m) lson->insert(p,q,c); else
		if (p>=m) rson->insert(p,q,c); else {
			lson->insert(p,m,c);
			rson->insert(m,q,c);
		}
}

void segtree::count(int &lc, int &rc) {
	if (color==no_color) return;
	if (color!=multi_color) {
		flags[color]++;
		lc=color;
		rc=color;
		return;
	}
	int t1=no_color,t2=no_color;
	lson->count(lc,t1);
	rson->count(t2,rc);
	if (t1==t2 && t1!=no_color) flags[t1]--;
}