很多學(xué)校流行一種比較的習(xí)慣。老師們很喜歡詢(xún)問(wèn)，從某某到某某當(dāng)中，分?jǐn)?shù)最高的是多少。?
這讓很多學(xué)生很反感。?

不管你喜不喜歡，現(xiàn)在需要你做的是，就是按照老師的要求，寫(xiě)一個(gè)程序，模擬老師的詢(xún)問(wèn)。當(dāng)然，老師有時(shí)候需要更新某位同學(xué)的成績(jī)。

Input

本題目包含多組測(cè)試，請(qǐng)?zhí)幚淼轿募Y(jié)束。?
在每個(gè)測(cè)試的第一行，有兩個(gè)正整數(shù) N 和 M ( 0<N<=200000,0<M<5000 )，分別代表學(xué)生的數(shù)目和操作的數(shù)目。?
學(xué)生ID編號(hào)分別從1編到N。?
第二行包含N個(gè)整數(shù)，代表這N個(gè)學(xué)生的初始成績(jī)，其中第i個(gè)數(shù)代表ID為i的學(xué)生的成績(jī)。?
接下來(lái)有M行。每一行有一個(gè)字符 C (只取'Q'或'U') ，和兩個(gè)正整數(shù)A，B。?
當(dāng)C為'Q'的時(shí)候，表示這是一條詢(xún)問(wèn)操作，它詢(xún)問(wèn)ID從A到B(包括A,B)的學(xué)生當(dāng)中，成績(jī)最高的是多少。?
當(dāng)C為'U'的時(shí)候，表示這是一條更新操作，要求把ID為A的學(xué)生的成績(jī)更改為B。?

Output

對(duì)于每一次詢(xún)問(wèn)操作，在一行里面輸出最高成績(jī)。

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 #include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> #include <math.h> using namespace std; #define INF 0x3f3f3f3f const int N=200000+5; int t,n,m; int tree[N<<2]; int a[N]; void PushUp(int rt){tree[rt] = tree[rt*2] + tree[rt*2+1]; ///區(qū)間和的更新操作 } void MaxPushUp(int rt){tree[rt] =max(tree[rt*2] , tree[rt*2+1]) ; ///區(qū)間和的更新操作 } void Build(int l,int r,int rt){// l,r 代表的是這個(gè)區(qū)間內(nèi)的左端點(diǎn) 和 右端點(diǎn)， rt代表的是 [l,r] 這個(gè)區(qū)間內(nèi)的值是存在哪一個(gè)位置的。if(l==r){//scanf("%d",&tree[rt]);tree[rt] = a[l];return;}int m=(l+r)/2;// 對(duì)于區(qū)間區(qū)分，我們一般將m點(diǎn)劃入左半邊區(qū)間Build(l,m,rt*2);Build(m+1,r,rt*2+1);MaxPushUp(rt); // PushUp 函數(shù)是通過(guò)2個(gè)子節(jié)點(diǎn)來(lái)更新現(xiàn)在這個(gè)節(jié)點(diǎn)的狀態(tài)， 對(duì)于不同的要求需要不同的寫(xiě)法。} int SumQuery(int l,int r,int rt,int L,int R){// [L,R]為查詢(xún)區(qū)間if(L<=l&&r<=R){return tree[rt];// 如果成立則滿足查詢(xún)區(qū)間覆蓋了當(dāng)前區(qū)間， 直接返回當(dāng)前區(qū)間的值}int m=(l+r)/2;int res=0;if(L<=m) res+=SumQuery(l,m,rt*2,L,R);//左邊有一部分需要查詢(xún)的區(qū)域。if(m<R) res+=SumQuery(m+1,r,rt*2+1,L,R);//右邊有一部分。return res;} int MaxQuery(int l,int r,int rt,int L,int R){// [L,R]為查詢(xún)區(qū)間if(L<=l&&r<=R){return tree[rt];// 如果成立則滿足查詢(xún)區(qū)間覆蓋了當(dāng)前區(qū)間， 直接返回當(dāng)前區(qū)間的值}int m=(l+r)/2;int res=-INF;if(L<=m) res=max(res,MaxQuery(l,m,rt*2,L,R));//左邊有一部分需要查詢(xún)的區(qū)域。if(m<R) res=max(res,MaxQuery(m+1,r,rt*2+1,L,R));//右邊有一部分。return res;} void AddUpdata(int l,int r,int rt,int L,int C){// l,r,rt 與前面的定義一樣， L代表的是要更新區(qū)間的位置，C代表的是修改后的值if(l==r){// 這里不能寫(xiě)成 if(l == L) 因?yàn)橛锌赡茏蠖它c(diǎn)恰好是要更新的位置， 但是還有右端點(diǎn)， 我們直接更新的只有區(qū)間 [L,L]。tree[rt]+=C;return ;}int m=(l+r)/2;if(L<=m) AddUpdata(l,m,rt*2,L,C);//要更新的區(qū)間在左邊部分，所以往左邊走，更新左邊else AddUpdata(m+1,r,rt*2+1,L,C);//要更新的區(qū)間在右邊部分， 往右邊走，更新右邊PushUp(rt);//更新完子節(jié)點(diǎn)之后需要更新現(xiàn)在的位置， 需要保證線段樹(shù)的性質(zhì)。 } void Updata(int l,int r,int rt,int L,int C){// l,r,rt 與前面的定義一樣， L代表的是要更新區(qū)間的位置，C代表的是修改后的值if(l==r){// 這里不能寫(xiě)成 if(l == L) 因?yàn)橛锌赡茏蠖它c(diǎn)恰好是要更新的位置， 但是還有右端點(diǎn)， 我們直接更新的只有區(qū)間 [L,L]。tree[rt]=C;return ;}int m=(l+r)/2;if(L<=m) Updata(l,m,rt*2,L,C);//要更新的區(qū)間在左邊部分，所以往左邊走，更新左邊else Updata(m+1,r,rt*2+1,L,C);//要更新的區(qū)間在右邊部分， 往右邊走，更新右邊MaxPushUp(rt);//更新完子節(jié)點(diǎn)之后需要更新現(xiàn)在的位置， 需要保證線段樹(shù)的性質(zhì)。 } int main() {while(scanf("%d%d",&n,&m)!=EOF){;for(int i = 1; i <= n; i++)scanf("%d", &a[i]);Build(1,n,1);char tmp[10];int i,j;while(m--){scanf("%s",tmp);scanf("%d%d",&i,&j);if(strcmp(tmp,"U")==0){Updata(1,n,1,i,j);}if(strcmp(tmp,"Q")==0){printf("%d\n",MaxQuery(1,n,1,i,j));}}}//cout << "Hello world!" << endl;return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的I Hate It的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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