HDU 1754 I Hate It，hdu1754
I Hate It
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 66742 Accepted Submission(s): 25969
Problem Description
很多學校流行一種比較的習慣。老師們很喜歡詢問，從某某到某某當中，分數最高的是多少。
這讓很多學生很反感。
不管你喜不喜歡，現在需要你做的是，就是按照老師的要求，寫一個程序，模擬老師的詢問。當然，老師有時候需要更新某位同學的成績。
Input
本題目包含多組測試，請處理到文件結束。
在每個測試的第一行，有兩個正整數 N 和 M ( 0<N<=200000,0<M<5000 )，分別代表學生的數目和操作的數目。
學生ID編號分別從1編到N。
第二行包含N個整數，代表這N個學生的初始成績，其中第i個數代表ID為i的學生的成績。
接下來有M行。每一行有一個字符 C (只取'Q'或'U') ，和兩個正整數A，B。
當C為'Q'的時候，表示這是一條詢問操作，它詢問ID從A到B(包括A,B)的學生當中，成績最高的是多少。
當C為'U'的時候，表示這是一條更新操作，要求把ID為A的學生的成績更改為B。
Output
對於每一次詢問操作，在一行裡面輸出最高成績。
Sample Input
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
Sample Output
5
6
5
9
Hint
Huge input,the C function scanf() will work better than cin
Author
linle
Source
2007省賽集訓隊練習賽（6）_linle專場
Recommend
lcy
題目大意：中文題面，不再贅述。
解題思路：線段樹的單點更新，區間最值問題。也是一道模板題，只要會模板即可。詳見代碼。
附上AC代碼：
![]()
1 #include <bits/stdc++.h>
2 #define lrt rt<<1
3 #define rrt rt<<1|1
4 #define lson l, m, lrt
5 #define rson m+1, r, rrt
6 using namespace std;
7 const int maxn = 200005;
8 int maxv[maxn<<2];
9 int n, q;
10 char op[5];
11
12 void push_up(int rt){
13 maxv[rt] = max(maxv[lrt], maxv[rrt]);
14 }
15
16 void build(int l, int r, int rt){
17 if (l == r){
18 int num;
19 scanf("%d", &num);
20 maxv[rt] = num;
21 return ;
22 }
23 int m = (l+r)>>1;
24 build(lson);
25 build(rson);
26 push_up(rt);
27 }
28
29 void modify(int p, int val, int l, int r, int rt){
30 if (l == r){
31 maxv[rt] = val;
32 return ;
33 }
34 int m = (l+r)>>1;
35 if (p <= m)
36 modify(p, val, lson);
37 else
38 modify(p, val, rson);
39 push_up(rt);
40 }
41
42 int query(int ql, int qr, int l, int r, int rt){
43 if (ql<=l && r<=qr)
44 return maxv[rt];
45 int m = (l+r)>>1;
46 int maxr = 0;
47 if (ql <= m)
48 maxr = max(maxr, query(ql, qr, lson));
49 if (qr > m)
50 maxr = max(maxr, query(ql, qr, rson));
51 return maxr;
52 }
53
54 int main(){
55 while (~scanf("%d%d", &n, &q)){
56 build(1, n, 1);
57 int a, b;
58 while (q--){
59 scanf("%s%d%d", op, &a, &b);
60 if (op[0] == 'Q')
61 printf("%d\n", query(a, b, 1, n, 1));
62 else
63 modify(a, b, 1, n, 1);
64 }
65 }
66 return 0;
67 }
View Code
