题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1610 貌似线段树的区间染色是一个非常常见的题型吧,但是不得不说。。我昨天刚刚碰到,而且统计每一种颜色占了多少个不连续区间的时候着实不会写,表示前面把树建出来和更新的步骤都是纯我自己写的,就是查找颜色个数那一步。。。不得不参考了,最后弄明白了。 如果一个区间没有染色或者有多种颜色,都会有标记,如果有了标记,就可以不用考虑这个结点了,直接找它的两个儿子就行了。如果证实某一个区间被染过色而且里面仅仅有一个颜色,那么就可以与其相邻子树比较然后再更新结果值(要求的是每种颜色占的不连续区间数量,相邻子树代表的是连续区间,所以就得这么比较),然后直接退出这个状态(都说了里面只有一个颜色,就没有找它儿子的必要了)。。
![](/Images/OutliningIndicators/ContractedBlock.gif) 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
|