问题描述

有n个格子，从左到右放成一排，编号为1-n。

共有m次操作，有3种操作类型：

1.修改一个格子的权值，

2.求连续一段格子权值和，

3.求连续一段格子的最大值。

对于每个2、3操作输出你所求出的结果。

输入格式

第一行2个整数n，m。

接下来一行n个整数表示n个格子的初始权值。

接下来m行，每行3个整数p,x,y，p表示操作类型，p=1时表示修改格子x的权值为y，p=2时表示求区间[x,y]内格子权值和，p=3时表示求区间[x,y]内格子最大的权值。

输出格式

有若干行，行数等于p=2或3的操作总数。

每行1个整数，对应了每个p=2或3操作的结果。

样例输入

4 3

1 2 3 4

2 1 3

1 4 3

3 1 4

样例输出

6

3

数据规模与约定

对于20%的数据n <= 100，m <= 200。

对于50%的数据n <= 5000，m <= 5000。

对于100%的数据1 <= n <= 100000，m <= 100000，0 <= 格子权值 <= 10000。

#include 
      
       #include
       
        #include
        
         #include
         
          #include 
          
           #define INF 1<<30using namespace std;struct node{    int r,l,Max,sum;}tree[100000*4];//线段树需要四倍的结点空间int Maxone(int a,int b){    return a>=b?a:b;}void build(int l,int r,int k){
    //建树    tree[k].l=l;    tree[k].r=r;    if(l==r){
    //左右端点相等为叶子结点        int s;        cin>>s;        tree[k].Max=s;        tree[k].sum=s;        return;    }    int m=(r+l)/2;//m是区间的中间点    build(l,m,2*k);//递归建立左右子树    build(m+1,r,2*k+1);//    tree[k].sum=tree[k*2].sum+tree[k*2+1].sum;//更新结点区间的和为左右子树结点的和    tree[k].Max=Maxone(tree[k*2].Max,tree[k*2+1].Max);//更新结点区间的最大值为左右子树最大值中较大的那个}void fix(int k,int x,int y){
    //修改结点的值    if(tree[k].l==tree[k].r){
    //当左右端点相等，则找到对应叶子结点        tree[k].sum=y;        tree[k].Max=y;        return;    }    int m=(tree[k].r+tree[k].l)/2;    if(x<=m) fix(2*k,x,y);    else fix(2*k+1,x,y);    tree[k].sum=tree[k*2].sum+tree[k*2+1].sum;//更新结点区间的和为左右子树结点的和    tree[k].Max=Maxone(tree[k*2].Max,tree[k*2+1].Max);//更新结点区间的最大值为左右子树最大值中较大的那个}int sum(int k,int x,int y){
    //求和    int ans=0;    if(tree[k].l>=x&&tree[k].r<=y){
    //当结点区间都在要求区间之内，则将区间的和加上，结束递归        ans=tree[k].sum;        return ans;    }    int m=(tree[k].r+tree[k].l)/2;    if(x<=m) ans+=sum(2*k,x,y);//当结点区间不都是在所要求得区间内，如果x<=m,则说明要求的区间存在左孩子中，则ans加上左孩子的那部分    if(y>m) ans+=sum(2*k+1,x,y);//如果y>m,则说明要求的区间存在右孩子中，则ans加上右孩子的那部分    return ans;}int findmax(int k,int x,int y){
    //求最大值     int mmax=0;     if(tree[k].l>=x&&tree[k].r<=y){        mmax=tree[k].Max;        return mmax;    }    int m=(tree[k].r+tree[k].l)/2;    if(x<=m) mmax=findmax(2*k,x,y);    if(y>m) {        int s=findmax(2*k+1,x,y);        mmax=s>mmax?s:mmax;    }    return mmax;}int main(){    int n,m;    cin>>n>>m;    build(1,n,1);    int p,x,y;    for(int i=0;i
           
            >p>>x>>y; if(p==1) fix(1,x,y); else if(p==2){ cout<
            
             <