1 #include <cstdio>
  2 #include <algorithm>
  3 #define lson l,m,rt<<1
  4 #define rson m+1,r,rt<<1|1
  5 using namespace std;
  6 
  7 const int maxn=5e4+5;
  8 int sum[maxn*4];  //sum求和，开四倍空间
  9 int Max[maxn*4];  //Max求最大值
 10 int Min[maxn*4];  //Min求最小值
 11 //int num[maxn];  //可以不存原数组下标[1,n]
 12 
 13 //up更新节点信息，这里是求和
 14 void up(int rt)
 15 {
 16     Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);
 17     Min[rt]=min(Min[rt<<1],Min[rt<<1|1]);
 18     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
 19 }
 20 //build建立线段树
 21 void build(int l,int r,int rt)
 22 {
 23     if(l==r)//若到达叶节点
 24     {
 25         scanf("%d",&sum[rt]); //可以不存储A数组的值
 26         Min[rt]=Max[rt]=sum[rt];
 27         return;
 28     }
 29     int m=(l+r)>>1;
 30     build(lson);   //左右递归
 31     build(rson);
 32     up(rt);   //更新信息
 33 }
 34 //单点增减
 35 void update(int p,int add,int l,int r,int rt)
 36 {
 37     if(l==r)//到达叶节点，修改叶节点的值
 38     {
 39         sum[rt]+=add;
 40         return;
 41     }
 42     int m=(l+r)>>1;
 43     //根据条件判断往左子树调用，还是往右
 44     if(p>m) update(p,add,rson);
 45     else update(p,add,lson);
 46     up(rt); //子节点更新了，本节点也要更新
 47 }
 48 //单点替换
 49 void update1(int p,int z,int l,int r,int rt)
 50 {
 51     if(l==r)
 52     {
 53         Max[rt]=Min[rt]=sum[rt]=z;
 54         return;
 55     }
 56     int m=(l+r)>>1;
 57     if(p<=m) update1(p,z,lson);
 58     else update1(p,z,rson);
 59     up(rt);
 60 }
 61 //查询区间和
 62 int query(int L,int R,int l,int r,int rt)
 63 {
 64     if(L<=l && r<=R) return sum[rt];  //区间内直接返回
 65     int m=(l+r)>>1;
 66     //累加答案
 67     int ret=0;
 68     if(L<=m) ret+=query(L,R,lson); //左子区间有重叠，递归
 69     if(R>m) ret+=query(L,R,rson); //右子区间有重叠，递归
 70     return ret;
 71 }
 72 //查询区间最大值
 73 int query1(int L,int R,int l,int r,int rt)
 74 {
 75     if(L<=l && r<=R)
 76     {
 77         return Max[rt];
 78     }
 79     int m=(l+r)>>1;
 80     int ret=-1;
 81     if(L<=m) ret=max(ret,query1(L,R,lson));
 82     if(R>m) ret=max(ret,query1(L,R,rson));
 83     return ret;
 84 }
 85 //查询区间最小值
 86 int query2(int L,int R,int l,int r,int rt)
 87 {
 88     if(L<=l && r<=R)
 89     {
 90         return Min[rt];
 91     }
 92     int m=(l+r)>>1;
 93     int ret=1e9;
 94     if(L<=m) ret=min(ret,query1(L,R,lson));
 95     if(R>m) ret=min(ret,query1(L,R,rson));
 96     return ret;
 97 }
 98 int main()
 99 {
100     int n,m;
101     while(~scanf("%d%d",&n,&m))
102     {
103         build(1,1,n);
104         while(m--)
105         {
106             char op[2];
107             int a,b;
108             scanf("%s%d%d",op,&a,&b);
109             if(op[0]==‘H‘) //区间求和
110                 printf("%d\n",query(a,b,1,n,1));
111             else if(op[0]==‘Q‘) //区间求最大
112             {
113                 /*  for(int i=1; i<=10; i++)
114                         printf("%d ",Max[i]);
115                     puts("");   */
116                 printf("%d\n",query1(a,b,1,n,1));
117             }
118             else if(op[0]==‘M‘) //区间求最小
119             {
120                 /*  for(int i = 1; i<=10; i++)
121                         printf("%d ",Min[i]);
122                     puts("");   */
123                 printf("%d\n",query2(a,b,1,n,1));
124             }
125             else if(op[0]==‘S‘) //单点增加
126                 update(a,b,1,n,1);
127             else if(op[0]==‘E‘) //单点减少
128                 update(a,-b,1,n,1);
129             else if(op[0]==‘U‘) //单点替换
130                 update1(a,b,1,n,1);
131         }
132     }
133     return 0;
134 }