作者:手机用户2602926865 | 来源:互联网 | 2023-09-23 13:22
I Hate It
http://acm.hdu.edu.cn/showproblem.php?pid=1754
线段树区间最大值,单点修改,区间查询。
code
#include
#include
#include using namespace std;const int N = 200005;
int tree[N << 2];#define ls(x) (x <<1)
#define rs(x) (x <<1 | 1)void push_up(int root) { tree[root] &#61; max(tree[ls(root)], tree[rs(root)]); }void build_tree(int l, int r, int root) {if (l &#61;&#61; r) {scanf("%d", &tree[root]);return;}int mid &#61; (l &#43; r) >> 1;build_tree(l, mid, ls(root));build_tree(mid &#43; 1, r, rs(root));push_up(root);
}int query(int l, int r, int root, int L, int R) {if (L <&#61; l && r <&#61; R) {return tree[root];}int mid &#61; (l &#43; r) >> 1;int res &#61; 0;if (L <&#61; mid) res &#61; max(res, query(l, mid, ls(root), L, R));if (mid < R) res &#61; max(res, query(mid &#43; 1, r, rs(root), L, R));return res;
}
void update(int l, int r, int root, int pos, int val) {if (l &#61;&#61; pos && r &#61;&#61; pos) {tree[root] &#61; val;return;}int mid &#61; (l &#43; r) >> 1;if (pos <&#61; mid) update(l, mid, ls(root), pos, val);else update(mid &#43; 1, r, rs(root), pos, val);push_up(root);
}int main() {int n, m;while (scanf("%d%d", &n, &m) !&#61; EOF) {memset(tree, 0, sizeof(tree));build_tree(1, n, 1);while (m--) {char c[5];int x, y;scanf("%s%d%d", c, &x, &y);if (c[0] &#61;&#61; &#39;Q&#39;) {printf("%d\n", query(1, n, 1, x, y));} else {update(1, n, 1, x, y);}}}return 0;
}