很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。
这让很多学生很反感。
不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。
#include <algorithm> #include <iostream> #include <cmath> #include <cstdio> #include <cstring> using namespace std; typedef long long LL; const LL N = 200000; int x[5 * N], n, a, b; /* 创建线段树 */ void creat(int d, int l, int r) { if(l == r) { scanf("%d", &x[d]); return ; } int m = (l + r) / 2; creat(2 * d, l, m); creat(2 * d + 1, m + 1, r); x[d] = max(x[2 * d], x[2 * d + 1]); } /* 查询模块 */ int query(int d, int l, int r) { if(a <= l && r <= b) return x[d]; int tmp = 0, m = l + (r - l) / 2; if(a <= m) tmp = max(tmp, query(2 * d, l, m)); if(b > m) tmp = max(tmp, query(2 * d + 1, m + 1, r)); return tmp; } /* 更新模块 */ void update(int d, int l, int r) { if(l == r) { x[d] = b; return ; } int m = l + (r - l) / 2; if(a <= m) update(2 * d, l, m); else update(2 * d + 1, m + 1, r); x[d] = max(x[2 * d], x[2 * d + 1]); } int main() { int m; while(~scanf("%d%d", &n, &m)) { int i; creat(1, 1, n); getchar(); char c; while(m--) { scanf("%c%d%d%*c", &c, &a, &b); if(c == ‘Q‘) { printf("%d\n", query(1, 1, n)); } else if(c == ‘U‘) { update(1, 1, n); } } } return 0; }
原文：http://www.cnblogs.com/yu0111/p/6710619.html