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

思路：線段樹模板題，求最值，要求可單點更新，區間查詢

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define PI acos(-1.0) #define E 1e-9 #define INF 0x3f3f3f3f #define N 200001 #define LL long long const int MOD=20091226; const int dx[]={-1,1,0,0}; const int dy[]={0,0,-1,1}; using namespace std;int maxx[N*4]; #define lson i*2,l,mid #define rson i*2+1,mid+1,rvoid pushUp(int i){maxx[i]=max(maxx[i*2],maxx[i*2+1]); } void build(int i,int l,int r){if(l==r){scanf("%d",&maxx[i]);return;}int mid=(l+r)/2;build(lson);build(rson);pushUp(i); }int queryInterval(int ql,int qr,int i,int l,int r){if(ql<=l&&r<=qr)return maxx[i];int mid=(l+r)/2;int res=-INF;if(ql<=mid)res=max(res,queryInterval(ql,qr,lson));if(mid<qr)res=max(res,queryInterval(ql,qr,rson));return res; }void updatePoint(int id,int val,int i,int l,int r){if(l==r){maxx[i]=val;return;}int mid=(l+r)/2;if(id<=mid)updatePoint(id,val,lson);elseupdatePoint(id,val,rson);pushUp(i); }int main(){int n,m;while(scanf("%d%d",&n,&m)!=EOF){build(1,1,n);while(m--){char str[5];int x,y;scanf("%s%d%d",str,&x,&y);if(str[0]=='Q')printf("%d\n",queryInterval(x,y,1,1,n));elseupdatePoint(x,y,1,1,n);}}return 0; }

?

總結

以上是生活随笔為你收集整理的I Hate It（HDU-1754）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。