1 #include <cstdio> 2 #include <iostream> 3 using namespace std; 4  5 typedef long long LL; 6 const int N=200010; 7  8 LL ans; 9 LL max(LL a,LL b){10     if(a>b) return a;11     else return b;    12 }13 14 struct Tree{15     LL l,r;16     LL MAX;17 };18 Tree tree[N*4];19 20 void pushup(LL x){21     LL tmp=2*x;22     tree[x].MAX=max(tree[tmp].MAX,tree[tmp+1].MAX);23 }24 25 void build(LL l,LL r,LL x){26     tree[x].l=l;27     tree[x].r=r;28     if(l==r){29         scanf("%lld",&tree[x].MAX);30         return ;31     }32     LL tmp=x<<1;33     LL mid=(l+r)>>1;34     build(l,mid,tmp);35     build(mid+1,r,tmp+1);36     pushup(x);     37 }38 39 40 void update(LL l,LL r,LL c,LL x){41     if(r<tree[x].l||l>tree[x].r) return ;42     if(l==tree[x].l&&r==tree[x].r){43         tree[x].MAX=c;44         return ;45     }46     LL tmp=x<<1;47     update(l,r,c,tmp);    48     update(l,r,c,tmp+1);49     pushup(x);50 }51 52 53 void query(LL l,LL r,LL x){54     if(r<tree[x].l||l>tree[x].r) return ;55     if(l<=tree[x].l&&r>=tree[x].r){56         if(ans<tree[x].MAX) ans=tree[x].MAX;57         return ;58     }59     LL tmp=x<<1;60     LL mid=(tree[x].l+tree[x].r)>>1;61     if(r<=mid) query(l,r,tmp);62     else if(l>mid) query(l,r,tmp+1);63     else{64         query(l,mid,tmp);65         query(mid+1,r,tmp+1);66     }67 }68 69 int main(){70     int n,m;71     while(scanf("%d %d",&n,&m)!=EOF){    72         build(1,n,1);73         char op;74         LL a,b;75         for(int i=1;i<=m;i++){76             getchar();77             scanf("%c",&op);78             scanf("%lld %lld",&a,&b);79             if(op==‘U‘){80                 update(a,a,b,1);81             }82             else if(op==‘Q‘){83                 ans=-11111;84                 query(a,b,1);85                 printf("%lld\n",ans);86             }87         }88     }89     return 0;90 }