Time Limit: 4000/2000 MS
(Java/Others) Memory Limit: 32768/32768 K
(Java/Others)
Total Submission(s): 14516 Accepted
Submission(s): 7176
思路：线段树，设计节点的时候不用记录该节点区间里面的sum，只需要记录每个区间里面的kind就行，（sum=R-L+1)*kind)，这样更新的时候就看当前节点区间和插入的区间[L,R]的关系：1，如果当前节点区间的kind和插入区间的kind相同就直接结束UpdateTree（）函数，不需要处理；2，否则，如果当前节点区间与插入区间正好匹配，把那么就直接把当前节点区间的kind置为插入区间的kind，结束UpdateTree（）函数；3，如果上述两条均不满足，则：（1）如果当前节点区间是纯色的（就是只有一种kind），那么该节点区间就变成不是纯色的了，（不止一种kind），那么就将该节点区间的kind变成0，同时注意更新其子区间的kind，因为我们并没有处理当前节点区间，而是把它转移到其子区间了。然后我们应该找该节点区间的子区间，直到满足1和2的条件（即是找到纯色区间或找到平匹配的区间）。（2）如果当前节点区间不是纯色那么就递归寻找其子区间，直到满足1,2条件。
1 /************************************************************************* 2 > File Name: Hook.cpp 3 > Author: wangzhili 4 > Mail: wangstdio.h@gmail.com 5 > Created Time: 2014/2/27 星期四 12:40:45 6 ************************************************************************/ 7 #include<iostream> 8 #include<cstdio> 9 using namespace std; 10 #define MAX 100000 11 class Tree_Node 12 { 13 public: 14 int left; 15 int right; 16 int mid; 17 int kind; 18 Tree_Node() 19 { 20 kind = 1; 21 } 22 }; 23 Tree_Node node[4*MAX]; 24 void BuildTree(int k, int l, int r) 25 { 26 node[k].left = l; 27 node[k].right = r; 28 node[k].kind = 1; 29 node[k].mid = (l + r) >> 1; 30 if(l == r) 31 return ; 32 int mid = (l + r) >> 1; 33 BuildTree(k << 1, l, mid); 34 BuildTree(k << 1|1, mid + 1, r); 35 } 36 37 void UpdateTree(int k, int l, int r, int kind) 38 { 39 if(node[k].left == l && node[k].right == r) 40 { 41 node[k].kind = kind; 42 return ; 43 } 44 if(node[k].kind == kind) 45 return ; 46 if(node[k].kind) 47 { 48 node[k << 1].kind = node[k].kind; 49 node[k << 1|1].kind = node[k].kind; 50 } 51 node[k].kind = 0; 52 if(node[k].mid < l) 53 UpdateTree(k << 1|1, l, r, kind); 54 else if(node[k].mid >= r) 55 UpdateTree(k << 1, l, r, kind); 56 else 57 { 58 UpdateTree(k << 1, l, node[k].mid, kind); 59 UpdateTree(k << 1|1, node[k].mid + 1, r,kind); 60 } 61 } 62 63 int GetSum(int k) 64 { 65 if(node[k].kind) 66 return (node[k].right-node[k].left + 1) * node[k].kind; 67 return GetSum(k << 1) + GetSum(k << 1|1); 68 } 69 70 int main(int argc, char const *argv[]) 71 { 72 int cnt, T, n, Q, i; 73 int l, r, kind; 74 cnt = 0; 75 // freopen("in.c", "r", stdin); 76 scanf("%d", &T); 77 while(T--) 78 { 79 cnt ++; 80 scanf("%d%d", &n, &Q); 81 BuildTree(1, 1, n); 82 for(i = 0; i < Q; i ++) 83 { 84 scanf("%d%d%d", &l, &r, &kind); 85 UpdateTree(1, l, r, kind); 86 } 87 printf("Case %d: The total value of the hook is %d.\n",cnt, GetSum(1)); 88 } 89 return 0; 90 }
原文：http://www.cnblogs.com/anhuizhiye/p/3571256.html