1 #include<cstdio>  2 #include<algorithm>  3 using namespace std;  4 const int Nmax=200005;  5 struct Node  6 {  7     int l;  8     int r;  9     int data; 10 }tree[Nmax*4]; 11 int n,m; 12 int num[Nmax]; 13 void push_up(int root) 14 { 15     tree[root].data=http://www.mamicode.com/max(tree[root].data,tree[root<<1].data); 16     tree[root].data=http://www.mamicode.com/max(tree[root].data,tree[root<<1|1].data); 17 } 18  19 void build(int root,int l,int r) 20 { 21     tree[root].l=l; 22     tree[root].r=r; 23     if(l==r) 24     { 25         tree[root].data=http://www.mamicode.com/num[l]; 26         return; 27     } 28     if(l<r) 29     { 30         int mid=(l+r)>>1; 31         build(root<<1,l,mid); 32         build(root<<1|1,mid+1,r); 33     } 34     push_up(root); 35 } 36  37 int query(int root,int l,int r) 38 { 39     if(tree[root].l==l && tree[root].r == r) 40     { 41         return tree[root].data; 42     } 43     int mid=(tree[root].l+tree[root].r)>>1; 44     if(mid<l) 45         return query(root<<1|1,l,r); 46     else if(mid>=r) 47         return query(root<<1,l,r); 48     else 49         return max(query(root<<1,l,mid),query(root<<1|1,mid+1,r)); 50 } 51  52 void update(int root,int l,int r,int data) 53 { 54     //if(tree[root].l>=l && tree[root].r<=r) 55     if(tree[root].l==l && tree[root].r == r) 56     { 57         tree[root].data=http://www.mamicode.com/max(tree[root].data,data); 58         return;     59     } 60     int mid=(tree[root].l+tree[root].r)>>1; 61     if(mid>=r) 62         update(root<<1,l,r,data); 63     else if(mid<l) 64         update(root<<1|1,l,r,data); 65     else 66     { 67         update(root<<1,l,mid,data); 68         update(root<<1|1,mid+1,r,data); 69     } 70     push_up(root); 71 } 72  73 void init() 74 { 75     for(int i=0;i<Nmax*4;i++) 76         tree[i].data=http://www.mamicode.com/0; 77 } 78  79 char c; 80 int x,y; 81  82 int main() 83 { 84     //freopen("in.in","r",stdin); 85     while(scanf("%d%d",&n,&m)==2) 86     { 87         init(); 88         for(int i=1;i<=n;i++) 89             scanf("%d",&num[i]); 90         build(1,1,n); 91         while(m--) 92         { 93             getchar(); 94             c=getchar(); 95             scanf("%d%d",&x,&y); 96             if(c==‘Q‘) 97                 printf("%d\n",query(1,x,y)); 98             else if(c==‘U‘) 99                 update(1,x,x,y);100             else101                 printf("ERROR!");102         }103     }104     return 0;105 }