1 #include <stdio.h> 2 #include <string.h> 3 #include <math.h> 4 #include <iostream> 5 #include <algorithm> 6 using namespace std; 7 const int MM=200002; 8 int num[MM<<2]; 9 void buildtree(int l,int r,int id)10 {11     if(l==r)12     {13         scanf("%d",&num[id]);return;14     }15     else16     {17         int mid=(l+r)>>1;18         buildtree(l,mid,id<<1);19         buildtree(mid+1,r,id<<1|1);20         num[id]=max(num[id<<1],num[id<<1|1]);21     }22 }23 int query(int L,int R,int l,int r,int id)24 { 25     int maxx=0x80000000;26     if(L<=l&&r<=R)return num[id];27     else28     {29         int mid=(l+r)>>1;30         if(L<=mid)31             maxx=max(query(L,R,l,mid,id<<1),maxx);32         if(R>mid)33             maxx=max(query(L,R,mid+1,r,id<<1|1),maxx);34         return maxx;35     }36     37 }38 void update(int pos,int e,int l,int r,int id)39 {40     if(l==r)41     {42         num[id]=e;43     }44     else45     {46         int mid=(l+r)>>1;47         if(pos<=mid)48             update(pos,e,l,mid,id<<1);49         else if(pos>mid)50             update(pos,e,mid+1,r,id<<1|1);51         num[id]=max(num[id<<1],num[id<<1|1]);52     }53 }54 int main()55 {56     int t,n,cas,i,x,y;57     char ch[2];58     59     while(~scanf("%d %d",&n,&t))60     {61         buildtree(1,n,1);62         while(t--)63         {64             scanf("%s %d %d",ch,&x,&y);65             if(ch[0]==‘U‘)66             {67                 update(x,y,1,n,1);68             }69             else70             {71                 printf("%d\n",query(x,y,1,n,1) );72             }73         }74         75     }76     return 0;77 }