Painting some colored segments on a line, some previously painted segments may be covered by some the subsequent ones.
Your task is counting the segments of different colors you can see at last.
Each of the following n lines consists of exactly 3 nonnegative integers separated by single spaces:
x1 x2 c
x1 and x2 indicate the left endpoint and right endpoint of the segment, c indicates the color of the segment.
All the numbers are in the range [0, 8000], and they are all integers.
Input may contain several data set, process to the end of file.
If some color can‘t be seen, you shouldn‘t print it.
Print a blank line after every dataset.
1 1
0 2
1 1
//#include <bits/stdc++.h> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <iostream> #include <algorithm> #include <iostream> #include <cstdio> #include <string> #include <cstring> #include <stdio.h> #include <queue> #include <stack>; #include <map> #include <set> #include <string.h> #include <vector> #define ME(x , y) memset(x , y , sizeof(x)) #define SF(n) scanf("%d" , &n) #define rep(i , n) for(int i = 0 ; i < n ; i ++) #define INF 0x3f3f3f3f #define mod 1000000007 #define PI acos(-1) using namespace std; typedef long long ll ; const int N = 100009; int n , last; int col[8010<<2] , ans[8010]; void pushdowm(int rt) { if(col[rt] != -1) { col[rt*2] = col[rt*2+1] = col[rt]; col[rt] = -1 ; return ; } } void update(int L , int R , int l , int r , int rt , int c) { if(l >= L && r <= R) { col[rt] = c ; return ; } if(col[rt] == c) return ; pushdowm(rt); int mid = ( l + r ) >> 1 ; if(L <= mid) update(L , R , l , mid , rt*2 , c); if(mid < R) update(L , R , mid+1 , r , rt*2+1 , c); } void query(int l , int r , int rt) { if(l == r) { if(col[rt] != -1 && col[rt] != last)//有颜色且与上一个颜色不同 { ans[col[rt]]++ ;//该种颜色块加一 } last = col[rt]; return ; } pushdowm(rt); if(l == r) return ; int mid = ( l + r ) >> 1 ; query(l , mid , rt*2); query(mid+1 , r , rt*2+1); } int main() { while(~scanf("%d" , &n)) { memset(col , -1 , sizeof(col)); for(int i = 0 ; i < n ; i++) { int x1 , x2 , c ; scanf("%d%d%d" , &x1 , &x2 ,&c); update(x1+1 , x2 , 1 , 8000 , 1 , c); } memset(ans , 0 , sizeof(ans)); last = -1 ; query(1 , 8000 , 1);//暴力搜索每一叶子 for(int i = 0 ; i <= 8000 ; i++)//暴力搜索每一种颜色 if(ans[i]) printf("%d %d\n" , i , ans[i]);//输出颜色，及多少块 cout << endl ; } return 0; }
原文：https://www.cnblogs.com/nonames/p/11609257.html