題目鏈接：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
|