鏈接：click here~~?
Problem Description
很多學(xué)校流行一種比較的習(xí)慣倔叼。老師們很喜歡詢問(wèn)肛度，從某某到某某當(dāng)中郑现，分?jǐn)?shù)最高的是多少夕春。
這讓很多學(xué)生很反感未荒。
不管你喜不喜歡，現(xiàn)在需要你做的是及志，就是按照老師的要求片排，寫一個(gè)程序，模擬老師的詢問(wèn)速侈。當(dāng)然率寡，老師有時(shí)候需要更新某位同學(xué)的成績(jī)。
Input
本題目包含多組測(cè)試倚搬，請(qǐng)?zhí)幚淼轿募Y(jié)束冶共。
在每個(gè)測(cè)試的第一行，有兩個(gè)正整數(shù) N 和 M ( 0
學(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í)候，表示這是一條詢問(wèn)操作叁征，它詢問(wèn)ID從A到B(包括A,B)的學(xué)生當(dāng)中纳账，成績(jī)最高的是多少。
當(dāng)C為'U'的時(shí)候航揉，表示這是一條更新操作塞祈，要求把ID為A的學(xué)生的成績(jī)更改為B。
Output
對(duì)于每一次詢問(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
【解題思路】：線段樹功能:update:單點(diǎn)替換 query:區(qū)間最值
代碼：
#include#include#include#include#include#include#include#include#include#includeusing namespace std;int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};#define mem(a) memset(a,0,sizeof(a))#define LL long long#define Max(a,b) a>b?a:b;#define Min(a,b) a>1;
build(lchild);
build(rchild);
Pushup(rt);
}
void update(int p,int add,int l,int r,int rt)? // 單點(diǎn)更新
{
if(l==r)
{
tree[rt]=add;
return ;
}
int m=(l+r)>>1;
if(p<=m) update(p,add,lchild);
else update(p,add,rchild);
Pushup(rt);
}
int query(int L,int R,int l,int r,int rt)? ? ? //區(qū)間查詢
{
if(L<=l&&r<=R)
{
return tree[rt];
}
int m=(l+r)>>1;
int sum=0;
if(L<=m) sum=max(sum,query(L,R,lchild));
if(R>m) sum=max(sum,query(L,R,rchild));
return sum;
}
int scan()
{
int res = 0, flag = 0;
char ch;
if((ch = getchar()) == '-') flag = 1;
else if(ch >= '0' && ch <= '9') res = ch - '0';
while((ch = getchar()) >= '0' && ch <= '9')
res = res * 10 + (ch - '0');
return flag ? -res : res;
}
int main()
{
int t,n,m,i,j,tot=1;
while(~scanf("%d%d",&n,&m))
{
build(1,n,1);
while(m--)
{
char op[10];
int a,b;
scanf("%s%d%d",op,&a,&b);
if(op[0]=='Q') printf("%d\n",query(a,b,1,n,1));
else update(a,b,1,n,1);
}
}
return 0;
}
