學生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
HintHuge input,the C function scanf() will work better than cin
AC代碼：
#include
#include
using namespace std;
int n,m;
struct tree
{
int l,r,key;
} node[600000];
int score[600000];
int X,Y;
int max(int x,int y)
{
return x>y?x:y;
}
int build(int l,int r,int i) //建樹
{
int mid=(l+r)/2;
node[i].l=l;
node[i].r=r;
if(l==r)
{
node[i].key=score[l];
return node[i].key;
}
else
{
node[i].key=max(build(l,mid,2*i),build(mid+1,r,2*i+1)); //子節點中的最大值給父親。
return node[i].key;
}
}
void update(int i,int x,int key)
{
node[i].key=max(node[i].key,key);
int mid=(node[i].l+node[i].r)/2;
if(node[i].l==node[i].r)
return ;
if(x>mid)
update(2*i+1,x,key); //x>mid往右邊的節點找
else
update(2*i,x,key);
}
int Quetion(int i,int l,int r)
{
if(node[i].l==l&&node[i].r==r)
return node[i].key;
else
{
int mid=(node[i].l+node[i].r)/2;
if(l<=mid&&r>=mid+1)
{
return max(Quetion(2*i,l,mid),Quetion(2*i+1,mid+1,r));
}
else if(l>=mid+1)
{
return Quetion(2*i+1,l,r);
}
else
{
return Quetion(2*i,l,r);
}
}
}
int main()
{
char ch;
int a,b;
while(scanf(%d %d,&n,&m)!=EOF)
{
int i;
for(i=1; i<=n; i++)
scanf(%d,&score[i]);
build(1,n,1);
while(m--)
{
getchar();
scanf(%c %d %d,&ch,&a,&b);
if(ch=='U')
update(1,a,b);
else
printf(%d
,Quetion(1,a,b));
}
}
return 0;
}
