ACwing 你能回答这些问题吗(线段树求最大连续字段和）

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

1、“1 x y”，查询区间 [x,y] 中的最大连续子段和，即 maxx≤l≤r≤ymaxx≤l≤r≤y{∑ri=lA[i]∑i=lrA[i]}。

2、“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≤500000,M≤100000N≤500000,M≤100000

输入样例：

5 3
1 2 -3 4 5
1 2 3
2 2 -1
1 3 2

输出样例：

2
-1

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
#include<cmath>const int maxn=5e5+;
typedef long long ll;
using namespace std;
struct node
{
    int l,r;
    ll sum,suml,sumr,summax;
}tree[maxn<<];
void pushup(int m)
{
    tree[m].sum=(tree[m<<].sum+tree[m<<|].sum);
    tree[m].summax=max(max(tree[m<<].summax,tree[m<<|].summax),tree[m<<].sumr+tree[m<<|].suml);
    tree[m].suml=max(tree[m<<].suml,tree[m<<].sum+tree[m<<|].suml);
    tree[m].sumr=max(tree[m<<|].sumr,tree[m<<].sumr+tree[m<<|].sum);
}
void build(int m,int l,int r)
{
    tree[m].l=l;
    tree[m].r=r;
    if(l==r)
    {
        scanf("%lld",&tree[m].sum);
        tree[m].summax=tree[m].sum;
        tree[m].suml=tree[m].sum;
        tree[m].sumr=tree[m].sum;
        return ;
    }
    int mid=(l+r)>>;
    build(m<<,l,mid);
    build(m<<|,mid+,r);
    pushup(m);
}
void update(int m,int pos,ll val)
{
    if(tree[m].l==tree[m].r&&tree[m].l==pos)
    {
        tree[m].sum=val;
        tree[m].summax=tree[m].sum;
        tree[m].suml=tree[m].sum;
        tree[m].sumr=tree[m].sum;
        return ;
    }
    int mid=(tree[m].l+tree[m].r)>>;
    if(pos<=mid)
    {
        update(m<<,pos,val);
    }
    else
    {
        update(m<<|,pos,val);
    }
    pushup(m);
}
node query(int m,int l,int r)
{
    if(tree[m].l==l&&tree[m].r==r)
    {
        return tree[m];
    }
    int mid=(tree[m].l+tree[m].r)>>;
    if(r<=mid)
    {
        return query(m<<,l,r);
    }
    else if(l>mid)
    {
        return query(m<<|,l,r);
    }
    else
    {
        node treel,treer,temp;
        treel=query(m<<,l,mid);
        treer=query(m<<|,mid+,r);
        temp.sum=treel.sum+treer.sum;
        temp.summax=max(max(treel.summax,treer.summax),treel.sumr+treer.suml);
        temp.suml=max(treel.suml,treel.sum+treer.suml);
        temp.sumr=max(treer.sumr,treer.sum+treel.sumr);
        return temp;
    }
}
int main()
{    int n,q;
    cin>>n>>q;
    build(,,n);
    int op,l,r;
    while(q--)
    {
        scanf("%d",&op);
        if(op==)
        {
            scanf("%d%d",&l,&r);
            if(l>r)
            {
                swap(l,r);
            }
            printf("%lld\n",query(,l,r).summax);
        }
        else
        {
            scanf("%d%d",&l,&r);            update(,l,r);
        }
    }
    return ;
}