程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ZOJ1610 Count the Colors 經典線段樹染色問題

ZOJ1610 Count the Colors 經典線段樹染色問題

編輯：C++入門知識

題意，給你n個 x,y,c，意思就是區間[x,y]被染成C色，但是顏色會被覆蓋的，染色操作完成以後問你每種顏色有多少段並輸出顏色編號id跟段數cnt

經典問題，不過寫的有點撮吧，沒去看別人的，這個方法應該是最傳統的最普通的，常規的開數組記錄，也許大神們有更高端的方法

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long

#define LL __int64

#define eps 1e-8

#define inf 0xfffffff

//const LL INF = 1LL<<61;

using namespace std;

//vector > G;
//typedef pair P;
//vector > ::iterator iter;
//
//mapmp;
//map::iterator p;

const int N = 8000 + 5;

typedef struct Node {
	int l,r;
	int col;
};

Node tree[N * 4];

int color[N];
int ans[N];

void init() {
	memset(color,-1,sizeof(color));
	memset(ans,0,sizeof(ans));
}

void build(int l,int r,int id) {
	tree[id].l = l;
	tree[id].r = r;
	tree[id].col = -1;
	if(l == r)return;
	int mid = (l + r)/2;
	build(l,mid,id<<1);
	build(mid+1,r,id<<1|1);
}

void cal(int id) {
	if(tree[id].col > -1) {
		tree[id<<1].col = tree[id].col;
		tree[id<<1|1].col = tree[id].col;
		tree[id].col = -1;
	}		
}

void update(int l,int r,int id,int col) {
	if(tree[id].col == col)return;
	if(l <= tree[id].l && r >= tree[id].r) {
		 tree[id].col = col;return;
	}
	cal(id);
	int mid = (tree[id].l + tree[id].r)/2;
	if(r <= mid)update(l,r,id<<1,col);
	else if(l > mid)update(l,r,id<<1|1,col);
	else {
		update(l,mid,id<<1,col);
		update(mid+1,r,id<<1|1,col);
	}
}

void query(int l,int r,int id) {
	if(tree[id].col > -1) {
		for(int i=tree[id].l;i<=tree[id].r;i++)
			color[i] = tree[id].col;
		return;
	}
	if(tree[id].l == tree[id].r)return;
	int mid = (tree[id].l + tree[id].r)/2;
	if(r <= mid)query(l,r,id<<1);
	else if(l > mid)query(l,r,id<<1|1);
	else {
		query(l,mid,id<<1);
		query(mid+1,r,id<<1|1);
	}
}

int main() {
	int n;
	while(scanf("%d",&n) == 1) {
		int q = n;
		init();
		build(1,N,1);
		int x,y,c;
		while(q--) {
			scanf("%d %d %d",&x,&y,&c);
			x++;
			update(x,y,1,c);
		}
		query(1,N,1);
		for(int i=1;i -1)
					ans[color[i]]++;
		for(int i=0;i