zoj 1610

1. 思维:

• 线段区间[1,8000],颜色区间[0,8000]
• 记录输入.找每个点的最后一个覆盖点就行了
• 然后算多少个颜色段

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

using namespace std;
const int maxn =  1e4;
int n;
int e[maxn][3];
int color[maxn];
int ans[maxn];
int main() {
//	freopen("a.txt","r",stdin);
	while (scanf("%d",&n) != EOF) {
		memset(ans,0,sizeof ans);
		memset(color,-1,sizeof color);
		
		for (int i=1; i<=n; i++) {
			scanf("%d%d%d",&e[i][0],&e[i][1],&e[i][2]);
			e[i][0]++;
		}
		for (int i=1; i<=8000; i++) //遍历每一个位置,找到最后一次覆盖这个位置的值
			for (int j=n; j>=1; j--) 
				if (e[j][0]<=i && i<=e[j][1]) {
					color[i] = e[j][2];
					break;
				}
		// 现在统计所有颜色段的值 都统计出来
//		for(int i=1; i<=right; i++) printf("%d ",color[i]); 
		int last = -99;
		for (int i=1; i<=8000; i++) {
			if (last == color[i]) continue;
			else {
				last = color[i];
				ans[color[i]]++;
			}
		}
		for (int i=0; i<= 8000; i++) {
			if (ans[i]) printf("%d %d\n",i,ans[i]);
		}
		printf("\n");
	}
	return 0;
}

2.线段树

• add() == -1因为颜色可能为0
• 线段树区间修改模板求出最后的所有点的颜色
• 统计颜色段

#include <iostream>
#include <string.h>
using namespace std;
const int maxn = 8010;
struct segementTree {
	int left,right;
	int add;
	#define left(x) tree[x].left
	#define right(x) tree[x].right
	#define add(x) tree[x].add
}tree[maxn*4];
int color[maxn];
int ans[maxn];
void build(int p,int left,int right) {
	right(p) = right; left(p) = left;
	add(p) = -1; // 颜色可能是0,
	if (left == right) return;
	int mid = (left + right)/2;
	build(2*p,left,mid);
	build(2*p+1,mid+1,right);
}
void pushDown(int p) {
	if (add(p) != -1) {
		add(2*p) = add(2*p+1) = add(p);
		add(p) = -1;
	}
}
void change(int p,int left,int right,int val) {
	if (left<=left(p) && right(p)<=right) {
		add(p) = val;
		return ;
	}
	pushDown(p);
	int mid = (left(p) + right(p))/2;
	if (left <= mid) change(2*p,left,right,val);
	if (mid < right) change(2*p+1,left,right,val);
}
void ask(int p,int left,int right) {
	if (left(p) == right(p)) {
		color[left(p)] = add(p);
		return ;
	}
	pushDown(p);
	int mid = (left(p) + right(p))/2;
	if (left <= mid) ask(2*p,left,right);
	if (mid < right) ask(2*p+1,left,right);
}
int main() {
//	freopen("a.txt","r",stdin);
	int n;
	while (scanf("%d",&n) != EOF) {
		memset(color,0,sizeof color);
		memset(ans,0,sizeof ans);
		build(1,1,8000);
		int u,v,w;
		for(int i=1; i<=n; i++) {
			scanf("%d%d%d",&u,&v,&w);
			u++;
//			printf("%d %d\n",u,v);
			change(1,u,v,w);
		}
		ask(1,1,8000);
		// 区间段的颜色已经维护出来
		int last = -99;
		for (int i=1; i<=8000; i++) {
			if (last == color[i]) continue;
			else {
				last = color[i];
				ans[color[i]]++;
			}
		}
		for (int i=0; i<= 8000; i++) {
			if (ans[i]) printf("%d %d\n",i,ans[i]);
		}
		printf("\n");
	}
	return 0;
}