操作格子

资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
有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。

题目来自于蓝桥杯练习库

如下的代码中演示了，如何直接修改一个位置上的值，以及如何求取一个区间的最大值。

• 直接修改一个位置的值 ： 由于线段树是会递归回溯的，因此你直接修改即可，那么相关区间的最大值以及区间的和都会在回溯的时候得到修改。
• 维护一段区间的最大值 ： 和维护一段区间的和极其的相似（代码结构都几乎相同），需要在原始结构体中再添加一个遍历maxv,然后在询问最大值的时候，就是不断的递归往下询问，被包含在询问区间内的小区间，就直接返回该区间内的maxv否则继续递归。
• 以上的两个操作都是基于yls的代码模板稍作修改即可，阅读下面代码前，请先背过原始模板。

代码

#include<iostream>

using namespace std;

const int N=100010;

struct TR
{
    int l;
    int r;
    int sum;
    int maxv;
}tr[4*N];
int w[N];
int n,m;

void pushup(int u){
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
    tr[u].maxv=max(tr[u<<1].maxv,tr[u<<1|1].maxv);
}

void build(int u,int l,int r){
    if(l==r) tr[u]={l,r,w[r],w[r]};
    else{
        int mid=l+r>>1;
        tr[u]={l,r};
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
}

int query(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;
    int mid=tr[u].r+tr[u].l>>1;
    int sum=0;
    if(l<=mid) sum+=query(u<<1,l,r);
    if(r>mid) sum+=query(u<<1|1,l,r);
    return sum;
}

void modify(int u,int x,int v){
    if(tr[u].l==tr[u].r){
        tr[u].sum=v;//直接把一点的值进行修改而不需要像树状数组那样+一个值再-一个值 
        tr[u].maxv=v;
    }else{
        int mid=tr[u].l+tr[u].r>>1;
        if(x<=mid) modify(u<<1,x,v);
        else modify(u<<1|1,x,v);
        pushup(u);
    }
}

int qmax(int u,int l,int r){//查找一段区间中的最大值 
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].maxv;
    int mid=tr[u].l+tr[u].r>>1;
    int Max=-1;
    if(l<=mid) Max=qmax(u<<1,l,r);
    if(r>mid) Max=max(Max,qmax(u<<1|1,l,r));

    return Max;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);

    build(1,1,n);

    while(m--){
        int k,a,b;
        scanf("%d%d%d",&k,&a,&b);
        if(k==1){
            modify(1,a,b);
        }else if(k==2){
            printf("%d\n",query(1,a,b));
        }else{
            printf("%d\n",qmax(1,a,b));
        }
    }

    return 0;
}