1 //Accepted    7172 KB    515 ms  2 //基础线段树  3 #include <cstdio>  4 #include <cstring>  5 #include <iostream>  6 using namespace std;  7 const int imax_n = 200005;  8 struct node  9 { 10     int l,r; 11     int tmax; 12 }f[imax_n*3]; 13 int a[imax_n]; 14 int n,m; 15 int max(int a,int b) 16 { 17     return a>b?a:b; 18 } 19 void build(int t,int l,int r) 20 { 21     f[t].l=l; 22     f[t].r=r; 23     if (l==r) 24     { 25         f[t].tmax=a[l]; 26         return ; 27     } 28     int mid=(l+r)/2; 29     build(2*t,l,mid); 30     build(2*t+1,mid+1,r); 31     f[t].tmax=max(f[2*t].tmax,f[2*t+1].tmax); 32 } 33 void change(int t,int l,int r,int c) 34 { 35     if (f[t].l==l && f[t].r==r) 36     { 37         f[t].tmax=c; 38         return ; 39     } 40  41     int mid=(f[t].l+f[t].r)/2; 42     //printf("mid=%d",mid); 43     if (r<=mid) change(2*t,l,r,c); 44     else 45     { 46         if (l>mid) change(2*t+1,l,r,c); 47         else 48         { 49             //change(2*t,l,mid,c); 50             //change(2*t+1,mid+1,r,c); 51         } 52     } 53     f[t].tmax=max(f[2*t].tmax,f[2*t+1].tmax); 54 } 55 int query(int t,int l,int r) 56 { 57     if (f[t].l==l && f[t].r==r) 58     { 59         return f[t].tmax; 60     } 61     int mid=(f[t].r+f[t].l)/2; 62     if (r<=mid) return query(2*t,l,r); 63     else 64     { 65         if (l>mid) return query(2*t+1,l,r); 66         else 67         { 68             return max(query(2*t,l,mid),query(2*t+1,mid+1,r)); 69         } 70     } 71 } 72 int main() 73 { 74     while (scanf("%d%d",&n,&m)!=EOF) 75     { 76         for (int i=1;i<=n;i++) 77         { 78             scanf("%d",&a[i]); 79         } 80         build(1,1,n); 81         char s[10]; 82         int x,y; 83         for (int i=0;i<m;i++) 84         { 85             scanf("%s%d%d",s,&x,&y); 86             if (s[0]==‘U‘) 87             change(1,x,x,y); 88             else 89             { 90                 if (x>y) 91                 { 92                     int t=x; 93                     x=y; 94                     x=t; 95                 } 96                 printf("%d\n",query(1,x,y)); 97             } 98         } 99     }100     return 0;101 }