文件详细信息

下载本文件

本文件的大小为 945 字节。

#include<algorithm>
#include<cstdio>
const int maxn=200005;
int n,m,grade[maxn];
char op;
int a,b;
int val[maxn<<2];
void pushup(int u){
	val[u]=std::max(val[u<<1],val[u<<1|1]);
}
void build(int u,int l,int r){
	if(l==r){
		val[u]=grade[l];
		return;
	}
	int m=(l+r)>>1;
	build(u<<1,l,m);
	build(u<<1|1,m+1,r);
	pushup(u);
}
void modify(int u,int l,int r,int x,int v){
	if(l==r){
		val[u]=std::max(val[u],v);
		return;
	}
	int m=(l+r)>>1;
	if(x<=m)modify(u<<1,l,m,x,v);
	else modify(u<<1|1,m+1,r,x,v);
	pushup(u);
}
int query(int u,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr)return val[u];
	int m=(l+r)>>1,ans=0;
	if(ql<=m)ans=query(u<<1,l,m,ql,qr);
	if(qr>m)ans=std::max(ans,query(u<<1|1,m+1,r,ql,qr));
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",grade+i);
	build(1,1,n); 
	while(m--){
		scanf("\n%c%d%d",&op,&a,&b);
		if(op=='Q')printf("%d\n",query(1,1,n,a,b));
		else modify(1,1,n,a,b);
	}
	return 0;
}