P1531

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node{
	int l,r,data;
}tree[N*4];
int n,m,a[N];
void build(int root,int l,int r)
{
	tree[root].l=l,tree[root].r=r;
	if(l==r)
	{
		tree[root].data=a[l];
		return ;
	}
	int mid=(l+r)/2;
	build(root*2,l,mid);
	build(root*2+1,mid+1,r);
	tree[root].data=max(tree[root*2].data,tree[root*2+1].data);
}
void updata(int root,int x,int k)
{
	if(tree[root].l==tree[root].r)
	{
		tree[root].data=k;
		return ;
	}
	int mid=(tree[root].l+tree[root].r)/2;
	if(x<=mid)
	{
		updata(root*2,x,k);
	}
	else
	{
		updata(root*2+1,x,k);
	}
	tree[root].data=max(tree[root*2].data,tree[root*2+1].data);
}
int query(int root,int l,int r)
{
	if(tree[root].l>=l && tree[root].r<=r)
	{
		return tree[root].data;
	}
	int mid=(tree[root].l+tree[root].r)/2,ans=-1;
	if(l<=mid)
	{
		ans=max(ans,query(root*2,l,r));
	}
	if(r>mid)
	{
		ans=max(ans,query(root*2+1,l,r));
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	build(1,1,n);
	while(m--)
	{
		char c;
		int x,y;
		scanf("%c%d%d",&c,&x,&y);
		if(c=='Q')
		{
			cout<<query(1,x,y)<<"\n";
			//printf("%d\n",query(1,x,y));
		}
		else
		{
			if(query(1,x,y)<y)
			{
				updata(1,x,y);
			}
		}
	}
	return 0;
}

提交记录