1 #include<cstdio> 2 #include<iostream> 3  4 using namespace std; 5 #define INF 0xffffff0 6 #define max(a,b) (a>b?a:b) 7 #define min(a,b) (a<b?a:b) 8 struct Node 9 {10     int maxV;11     int L, R;12     int Mid()13     {14         return (L+R)/2;15     }16 }Tree[800010];17 int maxV = 0;18 void BuildTree(int root,int L,int R);19 void Query(int root,int s,int e);20 void Insert(int root,int i,int v);//第i个数 为 V21 22 int main()23 {24     int N, M;25     while(scanf("%d%d",&N,&M) != EOF)26     {27         int k;28         BuildTree(0,1,N);29         for(int i = 1; i <= N; i++)30         {31             scanf("%d",&k);32             Insert(0,i,k);33         }34         while(M--)35         {36             int s, e;37             char str[2];38             maxV = 0;39             scanf("%s%d%d",str,&s,&e);40             if(str[0] == ‘Q‘)41             {42                 Query(0,s,e);43                 printf("%d\n",maxV);44             }45             else46                 Insert(0,s,e);47         }48     }49     return 0;50 }51 52 void BuildTree(int root,int L,int R)53 {54     Tree[root].L = L;55     Tree[root].R = R;56     Tree[root].maxV = 0;57     if(L != R)58     {59         BuildTree(root*2+1,L,Tree[root].Mid());60         BuildTree(root*2+2,Tree[root].Mid()+1,R);61     }62 }63 void Query(int root,int s,int e)64 {65     if(Tree[root].maxV <= maxV)66         return ;67     if(Tree[root].L == s && Tree[root].R == e)68     {69         maxV = max(Tree[root].maxV, maxV);70         return ;71     }72     if(e <= Tree[root].Mid())73         Query(root*2+1,s, e);74     else if( s > Tree[root].Mid())75         Query(root*2+2,s, e);76     else77     {78         Query(root*2+1,s,Tree[root].Mid());79         Query(root*2+2,Tree[root].Mid()+1,e);80     }81 }82 void Insert(int root,int i,int v)//第i个数 为 V83 {84     if(Tree[root].L == Tree[root].R)85     {86         Tree[root].maxV = v;87         return ;88     }89     Tree[root].maxV = max(v,Tree[root].maxV);90     if(i <= Tree[root].Mid())91         Insert(root*2+1,i,v);92     else93         Insert(root*2+2,i,v);94 }