杭电 hdu 1754 I Hate It （线段树 + 详细注释）

/* THE PROGRAM IS MADE BY PYY *//*----------------------------------------//    Copyright (c) 2011 panyanyany All rights reserved.    URL   : http://acm.hdu.edu.cn/showproblem.php?pid=1754    Name  : 1754 I Hate It    Date  : Wednesday, September 14, 2011    Time Stage : half an hour and one hour    Result: 46028212011-09-14 22:09:08Accepted1754484MS7160K2609 BC++pyy46028022011-09-14 22:07:05Output Limit Exceeded1754125MS7136K2660 BC++pyy46027852011-09-14 22:05:30Time Limit Exceeded17543000MS7132K2646 BC++pyy46025842011-09-14 21:45:47Time Limit Exceeded17543000MS7132K2525 BC++pyy46025632011-09-14 21:43:53Time Limit Exceeded17543000MS7132K2531 BC++pyy46025342011-09-14 21:40:48Time Limit Exceeded17543000MS7132K2531 BC++pyyTest Data :Review :一开始超时超得莫名其妙，艰苦调试之，发现一个很诡异的现象，就是Update() 竟然会自动执行多一次！一开始update() 函数的倒数第二句是这样写的：tree[root].max = max (update (2 * root, pos, val), update (2 * root + 1, pos, val)) ;于是为了观察其内部究竟是为何会多执行一次，别将其分立开来：int a, b ;a = update (2 * root, pos, val) ;b =update (2 * root + 1, pos, val) ;tree[root].max = max (a, b) ;发现它竟然又正常了！正在纳闷之际，猛然看到了max()函数的定义，竟然是宏定义：#define max(x1, y1) ((x1) > (y1) ? (x1) : (y1))于是一切豁然开朗，因为宏定义在展开的时候会这样：max (update (2 * root, pos, val), update (2 * root + 1, pos, val)) ;等同于：((update (2 * root, pos, val)) > (update (2 * root, pos, val)) ? (update (2 * root, pos, val)) : (update (2 * root, pos, val)))于是乎每次遇到max()展开之后就会出现四个update()函数，相当于多了指数级的执行次数！//----------------------------------------*/#include <stdio.h>#include <conio.h>#include <string.h>#define max(x1, y1) ((x1) > (y1) ? (x1) : (y1))#define min(x1, y1) ((x1) < (y1) ? (x1) : (y1))#define MAXSIZE 200002typedef struct {int max ;int left, right ;} NODE ;intn, m ;intnum [MAXSIZE] ;NODEtree[MAXSIZE * 20] ;// 构建线段树int build (int root, int left, int right){int mid ;// 当前节点所表示的区间tree[root].left= left ;tree[root].right= right ;// 左右区间相同，则此节点为叶子，max 应储存对应某个学生的值if (left == right){return tree[root].max = num[left] ;}mid = (left + right) / 2 ;// 递归建立左右子树，并从子树中获得最大值int a, b ;a = build (2 * root, left, mid) ;b = build (2 * root + 1, mid + 1, right) ;return tree[root].max = max (a, b) ;}// 从节点 root 开始，查找 left 和 right 之间的最大值int find (int root, int left, int right){int mid ;// 若此区间与 root 所管理的区间无交集if (tree[root].left > right || tree[root].right < left)return 0 ;// 若此区间包含 root 所管理的区间if (left <= tree[root].left && tree[root].right <= right)return tree[root].max ;// 若此区间与 root 所管理的区间部分相交int a, b ;// 不能这样 max (find(...), find(...));a = find (2 * root, left, right) ;b = find (2 * root + 1, left, right) ;return max (a, b) ;}// 更新 pos 点的值int update (int root, int pos, int val){// 若 pos 不存在于 root 所管理的区间内if (pos < tree[root].left || tree[root].right < pos)return tree[root].max ;// 若 root 正好是一个符合条件的叶子if (tree[root].left == pos && tree[root].right == pos)return tree[root].max = val ;// 否则。。。。int a, b ;// 不能这样 max (find(...), find(...));a = update (2 * root, pos, val) ;b =update (2 * root + 1, pos, val) ;tree[root].max = max (a, b) ;return tree[root].max ;}int main (){char c ;int i ;int x, y ;while (scanf ("%d%d", &n, &m) != EOF){for (i = 1 ; i <= n ; ++i)scanf ("%d", &num[i]) ;build (1, 1, n) ;for (i = 1 ; i <= m ; ++i){getchar () ;scanf ("%c%d%d", &c, &x, &y) ;if (c == 'Q'){printf ("%d\n", find (1, x, y)) ;}else{num[x] = y ;update (1, x, y) ;}}}return 0 ;}

1 楼 基德KID.1412 2011-09-16 Y神牛啊！！！顶顶顶，哈哈！ 2 楼 panyanyany 2011-09-17 基德KID.1412 写道Y神牛啊！！！顶顶顶，哈哈！
都是受华神渲染的结果啊！！