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;
  }