1 #include <algorithm>  2 #include <iostream>  3 #include <sstream>  4 #include <cstdlib>  5 #include <cstring>  6 #include <cstdio>  7 #include <string>  8 #include <bitset>  9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <list> 14 //#include <map> 15 #include <set> 16 using namespace std; 17 /***************************************/ 18 #define ll long long 19 #define int64 __int64 20 #define PI 3.1415927 21 /***************************************/ 22 const int INF = 0x7f7f7f7f; 23 const double eps = 1e-8; 24 const double PIE=acos(-1.0); 25 const int d1x[]= {0,-1,0,1}; 26 const int d1y[]= {-1,0,1,0}; 27 const int d2x[]= {0,-1,0,1}; 28 const int d2y[]= {1,0,-1,0}; 29 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 30 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 31 const int dirx[]= {-1,1,-2,2,-2,2,-1,1}; 32 const int diry[]= {-2,-2,-1,-1,1,1,2,2}; 33 /*vector <int>map[N];map[a].push_back(b);int len=map[v].size();*/ 34 /***************************************/ 35 void openfile() 36 { 37     freopen("data.in","rb",stdin); 38     freopen("data.out","wb",stdout); 39 } 40 priority_queue<int> qi1; 41 priority_queue<int, vector<int>, greater<int> >qi2; 42 /**********************华丽丽的分割线,以上为模板部分*****************/ 43 const int M=2000100; 44 struct tree 45 { 46     int sum;  //该区间的总和 47     int left,right;  //记录区间的左右闭区间坐标 48 } node[M*4];  //需开四倍的空间大小 49 int p[M];  //储存每个地点的人数数量 50 int cnt; 51 void build__tree(int id,int l,int r)  //建树 52 { 53     int mid=(l+r)/2; 54     node[id].left=l;   //初始化赋值区间的坐标 55     node[id].right=r; 56     if (l==r) 57     { 58         node[id].sum=p[l];  //初始化区间节点的val值 59         return ; 60     } 61     build__tree(id*2,l,mid);  //左孩子 62     build__tree(id*2+1,mid+1,r); //右孩子 63     //node[id].sum=node[id*2].sum+node[id*2+1].sum;//通过递归将各个区间节点val更新 64     if (node[id*2].sum>node[id*2+1].sum) 65         node[id].sum=node[id*2].sum; 66     else 67         node[id].sum=node[id*2+1].sum; 68 } 69 int query(int id,int l,int r)  //查询区间的总和 70 { 71     int mid=(node[id].left+node[id].right)/2; 72     if (node[id].left==l&&node[id].right==r) 73     { 74         // cnt+=node[id].sum;  //找到完全覆盖的区间将该区间的val加和。 75         if (node[id].sum>cnt) 76             cnt=node[id].sum; 77     } 78     else if (l>mid)   //[l，r]在右孩子部分 79         query(id*2+1,l,r); 80     else if (r<=mid) // [l，r]在左孩子部分 81         query(id*2,l,r); 82     else  //[l，r]区间，左右孩子都有分别递归。 83     { 84         query(id*2,l,mid); 85         query(id*2+1,mid+1,r); 86     } 87 } 88 void updata(int id,int pos,int val)  //从上向下寻找节点，找到节点后然后从下往上更新节点的val值 89 { 90     if (node[id].left==pos&&node[id].right==pos)//找到该节点 91     { 92         node[id].sum=val; 93         return ; 94     } 95     int mid=(node[id].left+node[id].right)/2; 96     if (pos<=mid)  //节点在左孩子部分 97         updata(id*2,pos,val); 98     else //节点在右孩子部分 99         updata(id*2+1,pos,val);100     //node[id].sum=node[id*2].sum+node[id*2+1].sum; //从下往上更新区间节点的值101     if (node[id*2].sum>node[id*2+1].sum)102         node[id].sum=node[id*2].sum;103     else104         node[id].sum=node[id*2+1].sum;105 }106 int main()107 {108     int cas;109     int n,m;110     char s[10];111     int i,j;112     while(scanf("%d%d",&n,&m)!=EOF)113     {114         for(i=1; i<=n; i++)115             scanf("%d",&p[i]);116         build__tree(1,1,n);117         while(m--)118         {119             scanf("%s",s);120             int x,y;121             if (s[0]==‘Q‘)122             {123                 scanf("%d%d",&x,&y);124                 cnt=-1;125                 query(1,x,y);126                 printf("%d\n",cnt);127             }128             else if (s[0]==‘U‘)129             {130                 scanf("%d%d",&x,&y);131                 updata(1,x,y);132             }133             else134                 break;135         }136     }137     return 0;138 }