AcWing 245. 你能回答这些问题吗 -526互联

给定长度为 $N$ 的数列 $A$ ，以及 $M$ 条指令，每条指令可能是以下两种之一：

1 x y，查询区间 $[x, y]$ 中的最大连续子段和，
2 x y，把 $A [x]$ 改成 $y$ 。

对于每个查询指令，输出一个整数表示答案。

输入格式

第一行两个整数 $N, M$ 。

第二行 $N$ 个整数 $A [i]$ 。

接下来 $M$ 行每行 $3$ 个整数 $k, x, y$ ， $k = 1$ 表示查询（此时如果 $x > y$ ，请交换 $x, y$ ）， $k = 2$ 表示修改。

输出格式

对于每个查询指令输出一个整数表示答案。

每个答案占一行。

数据范围

$N \leq 500000, M \leq 100000$ ,
$- 1000 \leq A [i] \leq 1000$

输入样例：

输出样例：

2
-1

代码实现：

#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int N=5e5+5;
int n,m;
int a[N];
struct node{
    int l,r;
    int tmax,lmax,rmax,sum;
}tr[4*N];
void pushup(node& u,node& l,node& r){
    u.sum=l.sum+r.sum;
    u.lmax=max(l.lmax,l.sum+r.lmax);
    u.rmax=max(r.rmax,l.rmax+r.sum);
    u.tmax=max(max(l.tmax,r.tmax),l.rmax+r.lmax);
}
void pushup(int u){
    pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void build(int u,int l,int r){
    if(l==r)tr[u]={l,l,a[l],a[l],a[l],a[l]};
    else{
        tr[u]={l,r};
        int mid=l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
void modify(int u,int x,int z){
    if(tr[u].l==x&&tr[u].r==x)tr[u]={x,x,z,z,z,z};
    else{
        int mid=tr[u].l+tr[u].r>>1;
        if(x<=mid)modify(u<<1,x,z);
        else modify(u<<1|1,x,z);
        pushup(u);
    }
}
node query(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r)return tr[u];
    int mid=tr[u].l+tr[u].r>>1;
    if(r<=mid)return query(u<<1,l,r);
    else if(l>mid)return query(u<<1|1,l,r);
    else{
        auto left=query(u<<1,l,r);
        auto right=query(u<<1|1,l,r);
        node res;
        pushup(res,left,right);
        return res;
    }
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    build(1,1,n);
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        if(a==1){
            if(b>c)swap(b,c);
            cout<<query(1,b,c).tmax<<endl;
        }else modify(1,b,c);
    }
    return 0;
}