【题意】:给出n个学生的初始成绩,编号1~n,不定时的修改某个学生的成绩和查询某一段连续编号成绩的最高值。(n<=200000)

【题解】:数据结构题目,线段树秒了,不知道树状数组行不行。

【代码】:
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 using namespace std;
 8 #define pb push_back
 9 #define MAX 200050
10 #define lc(x) (x << 1)
11 #define rc(x) (x << 1 | 1)
12 const int inf = 1 << 30;
13 int grade[MAX<<2], n, m;
14 
15 void pushup(int p) {
16     grade[p] = max(grade[lc(p)], grade[rc(p)]);
17 }
18 
19 void build(int l, int r, int p) {
20     if(l == r) {
21         scanf("%d", &grade[p]);
22         return;
23     }
24     int mid = (l + r) >> 1;
25     build(l, mid, lc(p));
26     build(mid + 1, r, rc(p));
27     pushup(p);
28 }
29 
30 int query(int L, int R, int l, int r, int p) {
31     int res = -inf; 
32     if(L == l && R == r) return grade[p];
33     int mid = (l + r) >> 1;
34     if(L > mid) res = max(res, query(L, R, mid + 1, r, rc(p)));
35     else if(R <= mid) res = max(res, query(L, R, l, mid, lc(p)));
36     else res = max(res, max(query(L, mid, l, mid, lc(p)), query(mid + 1, R, mid + 1, r, rc(p))));
37     return res;
38 }
39 
40 void update(int x, int val, int l, int r, int p) {
41     if(l == r) {
42         grade[p] = val;
43         return;
44     }
45     int mid = (l + r) >> 1;
46     if(x <= mid) update(x, val, l, mid, lc(p));
47     else update(x, val, mid + 1, r, rc(p));
48     pushup(p);
49 }
50 
51 int main() {
52     int a, b;
53     char str[10];
54     while(~scanf("%d%d", &n, &m)) {
55         build(1, n, 1);
56         while(m--) {
57             scanf("%s%d%d", str, &a, &b);
58             if(str[0] == 'Q') printf("%d\n", query(a, b, 1, n, 1));
59             else update(a, b, 1, n, 1);
60         }
61     }
62     return 0;
63 }