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 Pro ...
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
