学步园

/*<br /> Author: ACb0y<br /> Date: 2010-9-07<br /> Type: seg_tree<br /> ProblemId: hdu 1698<br /> Result: 2928262 2010-09-07 16:48:47 Accepted 1698 484MS 4324K 1762 B C++ ACb0y<br /> */</p> <p>#include <iostream><br /> using namespace std;</p> <p>//节点信息<br /> struct node<br /> {<br /> //区间<br /> int left;<br /> int right;<br /> //是否被全部涂成一个颜色<br /> int cover;<br /> //区间所涂的颜色<br /> int color;<br /> };</p> <p>//存储线段树数组（完全二叉树）<br /> node seg_tree[300000];</p> <p>//建树<br /> void buildTree(int left, int right, int loc)<br /> {<br /> seg_tree[loc].left = left;<br /> seg_tree[loc].right = right;<br /> seg_tree[loc].cover = seg_tree[loc].color = 1;<br /> //叶子节点返回<br /> if (left == right) return ;<br /> int mid = (left + right) >> 1;<br /> //建左子树<br /> buildTree(left, mid, loc * 2);<br /> //建右子树<br /> buildTree(mid + 1, right, loc * 2 + 1);<br /> }</p> <p>//更新树<br /> void updateTree(int left, int right, int value, int loc)<br /> {<br /> int LL = loc * 2;<br /> int RR = loc * 2 + 1;<br /> //如何更新的区间刚好是某个子树的区间则直接更新。<br /> if (seg_tree[loc].left == left && seg_tree[loc].right == right)<br /> {<br /> seg_tree[loc].cover = 1;<br /> seg_tree[loc].color = value;<br /> return ;<br /> }</p> <p> //如果树是被覆盖<br /> if (seg_tree[loc].cover)<br /> {<br /> seg_tree[loc].cover = 0;<br /> seg_tree[LL].cover = seg_tree[RR].cover = 1;<br /> seg_tree[LL].color = seg_tree[RR].color = seg_tree[loc].color;<br /> }</p> <p> int mid = (seg_tree[loc].left + seg_tree[loc].right) / 2;<br /> //如果要更新的区间在左子树中则更新左子树<br /> if (right <= mid)<br /> {<br /> updateTree(left, right, value, LL);<br /> }<br /> //如果要更新的区间在右子树，更新右子树<br /> else if (mid < left)<br /> {<br /> updateTree(left, right, value, RR);<br /> }<br /> //要更新的区间为于左右子树之间，则同时更新左子树和右子树<br /> else<br /> {<br /> updateTree(left, mid, value, LL);<br /> updateTree(mid + 1, right, value, RR);<br /> }<br /> }</p> <p>//查询区间和<br /> int queryTotal(int loc)<br /> {<br /> //如果区间是被覆盖的直接计算。<br /> if (seg_tree[loc].cover)<br /> {<br /> return (seg_tree[loc].right - seg_tree[loc].left + 1) * seg_tree[loc].color;<br /> }<br /> //否则求左右子树区间和的和。<br /> else<br /> {<br /> return queryTotal(loc * 2) + queryTotal(loc * 2 + 1);<br /> }<br /> }</p> <p>int main()<br /> {<br /> int T;<br /> int cas = 1;<br /> #ifndef ONLINE_JUDGE<br /> freopen("1698.txt", "r", stdin);<br /> #endif<br /> scanf("%d", &T);<br /> while (T--)<br /> {<br /> int n, q;<br /> scanf("%d%d", &n, &q);<br /> buildTree(1, n, 1);<br /> for (int i = 0; i < q; i++)<br /> {<br /> int x, y, z;<br /> scanf("%d%d%d", &x, &y, &z);<br /> updateTree(x, y, z, 1);<br /> }<br /> printf("Case %d: The total value of the hook is %d./n", cas++, queryTotal(1));<br /> }<br /> return 0;<br /> }<br />