简单线段树。
只需要单点修改。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5e5+5;
int xds[maxn<<2],a[maxn],n,m;
void pushup(int k){
xds[k]=max(xds[k<<1],xds[k<<1|1]);
}
void build(int k,int l,int r){
if(l==r){
xds[k]=a[l];
return ;
}
int mid=l+r>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
pushup(k);
}
void modify(int k,int l,int r,int x,int y){
if(l==r){
xds[k]=max(xds[k],y);
return ;
}
int mid=l+r>>1;
if(x<=mid)modify(k<<1,l,mid,x,y);
else modify(k<<1|1,mid+1,r,x,y);
pushup(k);
}
int query(int k,int l,int r,int x,int y){
if(x<=l&&r<=y)return xds[k];
int res=-0x3f3f3f3f,mid=l+r>>1;
if(x<=mid)res=max(res,query(k<<1,l,mid,x,y));
if(mid<y)res=max(res,query(k<<1|1,mid+1,r,x,y));
return res;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
build(1,1,n);
for(int i=1;i<=m;i++){
string c;
cin>>c;
int x,y;
cin>>x>>y;
if(c[0]==‘Q‘){
cout<<query(1,1,n,x,y)<<endl;
}else{
modify(1,1,n,x,y);
}
}
return 0;
}