Problem Description 很多學校流行一種比較的習慣。老師們很喜歡詢問，從某某到某某當中，分數(shù)最高的是多少。
這讓很多學生很反感。

不管你喜不喜歡，現(xiàn)在需要你做的是，就是按照老師的要求，寫一個程序，模擬老師的詢問。當然，老師有時候需要更新某位同學的成績。

?

Input 本題目包含多組測試，請?zhí)幚淼轿募Y束。
在每個測試的第一行，有兩個正整數(shù) N 和 M ( 0<N<=200000,0<M<5000 )，分別代表學生的數(shù)目和操作的數(shù)目。
學生ID編號分別從1編到N。
第二行包含N個整數(shù)，代表這N個學生的初始成績，其中第i個數(shù)代表ID為i的學生的成績。
接下來有M行。每一行有一個字符 C (只取'Q'或'U') ，和兩個正整數(shù)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專場 #include <cstdio> #include <iostream> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <queue> #include <vector> #include <map> using namespace std;#define ll long long #define eps 1e-9const int inf = 0x3f3f3f3f; const int mod = 1e9+7;int n, m, ans, a[2000000+8], x, y; char c;struct node {int l, r, sum; }tree[4*2000000+8];void build(int i, int l, int r)///建樹 {tree[i].sum = 0;tree[i].l = l;tree[i].r = r;if(l == r)///如果是葉子節(jié)點 {tree[i].sum = a[l];///則讓它的值存進去return ;}int mid = (tree[i].r+tree[i].l)/2;///如果不是葉子節(jié)點build(i*2, l, mid);///搜索左兒子的區(qū)間build(i*2+1, mid+1, r);///搜索右兒子的區(qū)間tree[i].sum = max(tree[i*2].sum , tree[i*2+1].sum);///使該區(qū)間最大的值往上傳 }void pls(int i, int pos, int k)///單點改變 {if(tree[i].r == pos && tree[i].l == tree[i].r)///如果時所要尋找的葉子節(jié)點 {tree[i].sum = k;///改變該點的值return ;}int mid = (tree[i].l+tree[i].r)/2;if(pos <= mid)///如果位置在左邊，就往左邊找pls(i*2, pos, k);else///否則往右邊找pls(i*2+1, pos, k);tree[i].sum = max(tree[i*2].sum , tree[i*2+1].sum);///不斷更新父親節(jié)點的最大值 }void search(int i, int l, int r) {if(tree[i].l >= l && tree[i].r <= r){ans = max(ans, tree[i].sum);return;}int mid = (tree[i].l+tree[i].r)/2;if(l <= mid)search(i*2, l, r);///區(qū)間不能寫成search(i*2, pos, k)，因為這樣區(qū)間會改變，但是題目要求要查的是[l, r]之間的最大值if(mid < r)search(i*2+1, l, r); }int main() {while(~scanf("%d%d", &n, &m) && (n+m)){for(int i = 1; i <= n; i++)scanf("%d", &a[i]);build(1, 1, n);for(int i = 1; i <= m; i++){ans = -1;getchar();scanf("%c %d %d", &c, &x, &y);if(c == 'Q'){search(1, x, y);printf("%d\n", ans);}else if(c == 'U'){pls(1, x, y);}}}return 0; }

?

轉載于:https://www.cnblogs.com/RootVount/p/11302748.html

總結

以上是生活随笔為你收集整理的HDU 1754 I Hate It（线段树单点更改、区间查找最大值）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。