题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1610 貌似线段树的区间染色是一个非常常见的题型吧，但是不得不说。。我昨天刚刚碰到，而且统计每一种颜色占了多少个不连续区间的时候着实不会写，表示前面把树建出来和更新的步骤都是纯我自己写的，就是查找颜色个数那一步。。。不得不参考了，最后弄明白了。 如果一个区间没有染色或者有多种颜色，都会有标记，如果有了标记，就可以不用考虑这个结点了，直接找它的两个儿子就行了。如果证实某一个区间被染过色而且里面仅仅有一个颜色，那么就可以与其相邻子树比较然后再更新结果值（要求的是每种颜色占的不连续区间数量，相邻子树代表的是连续区间，所以就得这么比较），然后直接退出这个状态（都说了里面只有一个颜色，就没有找它儿子的必要了）。。
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 #define lson l, m, rt << 1
9 #define rson m, r, rt << 1 | 1
10 const int maxn = 8010;
11 int col[maxn << 2], temp, num[maxn];
12 void PushDown(int rt)
13 {
14 if (col[rt] >= 0)
15 {
16 col[rt << 1] = col[rt];
17 col[rt << 1 | 1] = col[rt];
18 col[rt] = -2;
19 }
20 }
21 void build(int l, int r, int rt)
22 {
23 col[rt] = -1;
24 if (l == (r - 1)) return;
25 int m = (l + r) >> 1;
26 build(lson);
27 build(rson);
28 }
29 void update(int ll, int rr, int c, int l, int r, int rt)
30 {
31 if (col[rt] == c) return;
32 if (ll <= l && rr >= r)
33 {
34 col[rt] = c;
35 return;
36 }
37 PushDown(rt);
38 int m = (l + r) >> 1;
39 if (ll < m) update(ll, rr, c, lson);
40 if (rr > m) update(ll, rr, c, rson);
41 }
42 void countt(int l, int r, int rt)
43 {
44 if (col[rt] != -1 && col[rt] != -2)
45 {
46 if (col[rt] != temp)
47 {
48 num[col[rt]]++;
49 temp = col[rt];
50 }
51 return;
52 }
53 int m = (l + r) >> 1;
54 if (l != (r - 1))
55 {
56 countt(lson);
57 countt(rson);
58 }
59 else temp = -1;
60 }
61 int main()
62 {
63 int t;
64 while (scanf("%d", &t) != EOF)
65 {
66 memset(num, 0, sizeof(num));
67 build(0, 8000, 1);
68 while (t--)
69 {
70 int x, y, z;
71 scanf("%d%d%d", &x, &y, &z);
72 update(x, y, z, 0, 8000, 1);
73 }
74 countt(0, 8000, 1);
75 for (int i = 0; i <= 8000; i++) if (num[i]) printf("%d %d\n", i, num[i]);
76 cout << endl;
77 }
78 return 0;
79 }
80
|