不多说和上题差不多,同样的模板。。好好想想。。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 200000
int max(int a,int b)
{
a=a>b?a:b;
return a;
}
struct point
{
int x,y;
int max,sum;
}a[N*3];
void tree(int t,int x,int y)
{
a[t].x=x;
a[t].y=y;
a[t].max=0;
if(x==y)
return ;
int temp=2*t;
int mid=(x+y)/2;
tree(temp,x,mid);
tree(temp+1,mid+1,y);
}
void IN(int t,int x,int y)
{
if(a[t].x==a[t].y)
{
a[t].max=y;
return ;
}
int temp=2*t;
int mid=(a[t].x+a[t].y)/2;
if(x<=mid)
IN(temp,x,y);
else
IN(temp+1,x,y);
a[t].max=max(a[temp].max,a[temp+1].max);
}
int find(int t,int x,int y)
{
if(a[t].x==x&&a[t].y==y)
return a[t].max;
int temp=2*t;
int mid=(a[t].x+a[t].y)/2;
if(y<=mid)
return find(temp,x,y);
else if(x>mid)
return find(temp+1,x,y);
else
return max(find(temp,x,mid),find(temp+1,mid+1,y));
}
int main()
{
int n,m,i,k;
char str[100];
while(scanf("%d%d",&n,&m)!=EOF)
{
tree(1,1,n);
for(i=1;i<=n;i++)
{
scanf("%d",&k);
IN(1,i,k);
}
int x,y;
while(m--)
{
scanf("%s%d%d",str,&x,&y);
if(str[0]=='Q')
{
printf("%d\n",find(1,x,y));
}
else
IN(1,x,y);
}
}
return 0;
}