[ZOJ1610]Count the Colors(线段树，区间染色，单点查询)

题目链接：http://www.icpc.moe/onlinejudge/showProblem.do?problemCode=1610

　　题意：给一个长8000的绳子，向上染色。一共有n段被染色，问染色后共有多少不同的色段。注意假如相邻两个线段同色，那么算作一条线段。

　　线段树区间更新，不需要pushUP操作，因为查询和非叶节点无关。找长线段的时候首先定位最靠左那根，然后判后面是否与前面的线段颜色相等。注意有可能出现两条线段中间没有染色的情况，这时候查询返回一个无关值，这时候重置p即可。

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <iomanip>
  4 #include <cstring>
  5 #include <climits>
  6 #include <complex>
  7 #include <fstream>
  8 #include <cassert>
  9 #include <cstdio>
 10 #include <bitset>
 11 #include <vector>
 12 #include <deque>
 13 #include <queue>
 14 #include <stack>
 15 #include <ctime>
 16 #include <set>
 17 #include <map>
 18 #include <cmath>
 19 
 20 using namespace std;
 21 
 22 #define fr first
 23 #define sc second
 24 #define pb(a) push_back(a)
 25 #define Rint(a) scanf("%d", &a)
 26 #define Rll(a) scanf("%I64d", &a)
 27 #define Rs(a) scanf("%s", a)
 28 #define Fread() freopen("in", "r", stdin)
 29 #define Fwrite() freopen("out", "w", stdout)
 30 #define Rep(i, n) for(int i = 0; i < (n); i++)
 31 #define For(i, a, n) for(int i = (a); i < (n); i++)
 32 #define Cls(a) memset((a), (0), sizeof(a))
 33 #define Clr(a, x) memset((a), (x), sizeof(a))
 34 #define Full(a) memset((a), 0x7f7f, sizeof(a))
 35 
 36 #define lson l, m, rt << 1
 37 #define rson m + 1, r, rt << 1 | 1
 38 const int maxn = 8010;
 39 int sum[maxn<<2];
 40 int vis[maxn];
 41 int n, a, b, c;
 42 
 43 void pushDOWN(int rt) {
 44     if(sum[rt] != -1) {
 45         sum[rt<<1] = sum[rt<<1|1] = sum[rt];
 46         sum[rt] = -1;
 47     }
 48 }
 49 
 50 void update(int L, int R, int c, int l, int r, int rt) {
 51     if(L <= l && r <= R) {
 52         sum[rt] = c;
 53         return;
 54     }
 55     pushDOWN(rt);
 56     int m = (l + r) >> 1;
 57     if(L <= m) update(L, R, c, lson);
 58     if(R > m) update(L, R, c, rson);
 59 }
 60 
 61 int query(int p, int l, int r, int rt) {
 62     if(l == r) {
 63         return sum[rt];
 64     }
 65     pushDOWN(rt);
 66     int m = (l + r) >> 1;
 67     if(p <= m) return query(p, lson);
 68     else return query(p, rson);
 69 }
 70 
 71 int main() {
 72     // Fread();
 73     while(~Rint(n)) {
 74         int lo = 0x7f7f;
 75         Clr(sum, -1); Cls(vis);
 76         Rep(i, n) {
 77             Rint(a), Rint(b), Rint(c);
 78             lo = min(lo, a+1);
 79             update(a+1, b, c, 1, 8000, 1);
 80         }
 81         int p = query(lo, 1, 8000, 1);
 82         vis[p]++;
 83         For(i, lo+1, 8001) {
 84             int t = query(i, 1, 8000, 1);
 85             if(t == -1) {
 86                 p = -1;
 87                 continue;
 88             }
 89             if(t != p) {
 90                 vis[t]++;
 91                 p = t;
 92             }
 93 
 94         }
 95         Rep(i, 8001) {
 96             if(vis[i]) printf("%d %d
", i, vis[i]);
 97         }
 98         printf("
");
 99     }
100     return 0;
101 }