题目描述

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

1、“1 x y”，查询区间 [x,y] 中的最大连续子段和，即 max x≤l≤r≤y
maxx≤l≤r≤y
{∑ r i=l A[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≤100000
N≤500000,M≤100000

样例

输入样例：
5 3
1 2 -3 4 5
1 2 3
2 2 -1
1 3 2


输出样例：
2
-1

算法1

对于一个固定区间，求最大子段和我们有O(n)
的算法。但是如何维护不同区间的LIS
就成了一个问题。我们选择线段树解决区间问题，但使用线段树的话，我们需要明白，维护什么值，以及如何进行区间操作。

那么我们思考，对于相邻的两个区间，他们的LIS
有几种可能？
1. 左侧区间的LIS

1. 右侧区间的LIS

2. 两个区间合并后，中间新连接的部分
   前两点都好理解，针对第三点我们继续思考，中间部分能够成为LIS
   ，其实就是我们从连接部分分别向前向后，获得一个尽可能大的前/后缀和。那么我们维护或者合并区间的LIS
   就需要维护三个值，区间最大子段和，最大前缀和，最大后缀和。而我们在合并区间的时候，如何维护前/后缀和呢？我们需要多维护一个区间和。

整理我们得到，定义区间ls,rs
合并得到区间d，每个区间维护区间和sum
，区间最大字段和maxs
，区间最大前缀和maxl
，区间最大后缀和maxr
。则合并区间时，可得关系如下
1. d.sum=ls.sum+rs.sum

1. d.maxs=max(ls.maxs,rs.maxs,ls.maxr+rs.maxl)

2. d.maxl=max(ls.maxl,ls.sum+rs.maxl)

3. d.maxr=max(rs.maxr,rs.sum+ls.maxr)

用线段树维护即可

C++ 代码

#include<stdio.h>
#include<iostream>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
typedef long long ll;
const int N=500001;
ll maxn(ll a,ll b,ll c )
{
    if(a>=b&&a>=c)
    return a;
    if(b>=a&&b>=c)
    return b;
    if(c>=a&&c>=b)
    return c;
}
struct Node{
    int l,r;
    ll lmax,rmax,sum,dat;
    int mid()
    {
        return (l+r)>>1;
    }
}tree[N<<2];
void pushup(int rt)
{
    tree[rt].lmax=maxn(tree[rt<<1].sum,tree[rt<<1].sum+tree[rt<<1|1].lmax,tree[rt<<1].lmax);
    tree[rt].rmax=maxn(tree[rt<<1|1].sum,tree[rt<<1|1].sum+tree[rt<<1].rmax,tree[rt<<1|1].rmax);
    tree[rt].dat=maxn(tree[rt<<1].dat,tree[rt<<1|1].dat,tree[rt<<1].rmax+tree[rt<<1|1].lmax);
    tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
}

void build(int l,int r,int rt)
{
    tree[rt].l=l;
    tree[rt].r=r;

    if(l==r)
    {
        scanf("%lld",&tree[rt].dat);
        tree[rt].sum=tree[rt].lmax=tree[rt].rmax=tree[rt].dat;

        return;
    }
    int m=tree[rt].mid();
    build(lson);
    build(rson);
    pushup(rt);
}
void update(int rt,int x,int y )
{
    if(tree[rt].l==tree[rt].r)
    {

        tree[rt].sum=tree[rt].lmax=tree[rt].rmax=tree[rt].dat=y;
        return;
    }
    int m=tree[rt].mid();
    if(x<=m) update(rt<<1,x,y);
    else update(rt<<1|1,x,y);
    pushup(rt);
}
Node query(int rt, int l, int r){
    if(tree[rt].l==l && tree[rt].r==r)
    {
        return tree[rt];
    }


    int m = tree[rt].mid();
    if(m >= r)
        return query(rt<<1, l, r);
    else if(m < l)
        return query(rt<<1|1, l, r);
    else {
        Node ls = query(lson);
        Node rs = query(rson);
        Node ans;
        ans.dat = maxn(ls.dat, rs.dat, ls.rmax+rs.lmax);
        ans.lmax = maxn(ls.sum,ls.lmax, ls.sum+rs.lmax);
        ans.rmax = maxn(rs.sum,rs.rmax, rs.sum+ls.rmax);
        ans.sum  = ls.sum + rs.sum;

        return ans;
    }
}

int main()
{
    int n,m;
    cin>>n>>m;
    build(1,n,1);
    int i;int j,t;

    for(i=0;i<m;i++)
    {
        scanf("%d",&j);
        if(j==1)
        {
            int a,b;
            scanf("%d %d",&a,&b);
            if(a>b)
            {
                swap(a,b);
            }

            Node ans=query(1,a,b);
            cout<<ans.dat<<endl;

        }
        else
        {
            int x,y;
            scanf("%d %d",&x,&y);
            update(1,x,y);
        }
    }

}