#include<iostream>
#include<stdio.h>
using namespace std;
#define MAX 200001
int big;
struct Node
{
int r,l,max;
}s[MAX*3];
int Max(int a,int b)
{
return a>b?a:b;
}
void creat(int i,int a,int b)
{
s[i].l=a;
s[i].r=b;
s[i].max=0;
if(a==b)
return;
else
{
int mid=(a+b)>>1;
creat(i*2,a,mid);
creat(i*2+1,mid+1,b);
}
}
void updata(int i,int x,int y)
{
if(s[i].l==x&&s[i].r==x)
s[i].max=y;
else
{
int mid=(s[i].r+s[i].l)>>1;
if(x<=mid)
updata(i*2,x,y);
else
updata(i*2+1,x,y);
if(s[i].max<y)
s[i].max;
}
if(y>s[i].max)
s[i].max=y;
}
void find(int i,int a,int b)
{
if(s[i].l==a&&s[i].r==b)
{
if(big<s[i].max)
big=s[i].max;
}
else
{
int mid=(s[i].r+s[i].l)>>1;
if(a>mid)
find(i*2+1,a,b);
else if(b<=mid)
find(i*2,a,b);
else
{
find(i*2,a,mid);
find(i*2+1,mid+1,b);
}
}
}
int main()
{
int m,n;
while(scanf("%d %d",&n,&m)!=EOF)
{
creat(1,1,n);
for(int i=1;i<=n;i++)
{
int a;
scanf("%d",&a);
updata(1,i,a);
}
for(int i=1;i<=m;i++)
{
char a;
int b,c;
scanf("%*c %c",&a);
scanf("%d %d",&b,&c);
if(a=='Q')
{
big=0;
find(1,b,c);
cout<<big<<endl;
}
else
updata(1,b,c);
}
}
return 0;
}
转载于:https://www.cnblogs.com/cyiner/archive/2011/07/13/2104947.html
