題意：說的很清楚，不必過多的解釋了……
思路：線段樹的求區間最值……解釋在代碼裡
AC代碼：
[cpp]
/*
線段樹 -求區間最值之改點
1：線段樹中存的是 區間的最值
2：建線段樹時 到單點時回溯回去，更新出該點父節點（一直向上到根節點）的最值
3：改變某一點值時，找到該點所在區間節點，回溯回去，更新父節點的最值
4：查詢區間最值時，找到對應的的所有小區間，求出最值即可。
*/
#include<stdio.h>
#include<string.h>
#define Max 4*1000000
#define LL(a) a<<1; //2*A
#define RR(a) a>>1|1; //2*a+1
#define Mid(x,y) (x+y)>>1 //(x+y)/2
int A[Max],ans,cnt;
struct hello
{
int l;
int r;
int max; //存的是該區間的最值
}tree[Max];
void Build_tree(int l,int r,int t) // l,r 表示區間，t表示 區間節點
{
int x;
tree[t].l=l;
tree[t].r=r;
tree[t].max=0;
if(l==r)
{
while(t)
{
if(tree[t].max<A[l])
tree[t].max=A[l];
t/=2;
}
return ;
}
x=Mid(l,r);
Build_tree(l,x,2*t);
Build_tree(x+1,r,2*t+1);
}
void Updata_tree(int l,int r,int t)
{
if(tree[t].l==l&&tree[t].r==r)
{
tree[t].max=cnt;
while(t)
{
t/=2;
tree[t].max= tree[2*t].max>tree[2*t+1].max?tree[2*t].max:tree[2*t+1].max;
}
return ;
}
int x=Mid(tree[t].l,tree[t].r);
if(x>=r)
Updata_tree(l,r,2*t);
else if(x+1<=l)
Updata_tree(l,r,2*t+1);
else
{
Updata_tree(l,x,2*t);
Updata_tree(x+1,r,2*t+1);
}
}
void Query_tree(int l,int r,int t)
{
if(tree[t].l==l&&tree[t].r==r)
{
if(ans<tree[t].max)
ans=tree[t].max;
return ;
}
int x=Mid(tree[t].l,tree[t].r);
if(x>=r)
Query_tree(l,r,2*t);
else if(x+1<=l)
Query_tree(l,r,2*t+1);
else
{
Query_tree(l,x,2*t);
Query_tree(x+1,r,2*t+1);
}
}
int main()
{
int i,j,n,m,ncase;
while(~scanf("%d%d",&n,&m))
{
for(i=1;i<=n;i++)
scanf("%d",&A[i]);
Build_tree(1,n,1);
while(m--)
{
char str[10];
int x,y;
scanf("%s%d%d",str,&x,&y);
if(str[0]=='Q')
{
ans=0;
Query_tree(x,y,1);
printf("%d\n",ans);
}
else
{
cnt=y;
Updata_tree(x,x,1);
}
}
}
}
