danihao123's Blog

这题是很经典的线段树题。

我们可以发现最长子序列或跨越中点，或不跨越中点。若不跨越则肯定在左子或右子中，跨越则是左子最大后缀和和右子最大前缀和之和。问题便迎刃而解。（当然，求区间最大前缀/后缀和要用上区间和）

需注意此题可能会出现a>b！

代码：

/**************************************************************
    Problem: 1756
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2604 ms
    Memory:49648 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=500001;
struct Node{
    int L,R;
    int maxP,maxS,ans,sum;
};
Node Tree[maxn*4];
int A[maxn];
void merge(Node& O,Node& LC,Node& RC){
    O.sum=LC.sum+RC.sum;
    O.maxP=max(LC.maxP,LC.sum+RC.maxP);
    O.maxS=max(RC.maxS,RC.sum+LC.maxS);
    O.ans=max(max(LC.ans,RC.ans),LC.maxS+RC.maxP);
}
void maintain(int o){
    Node& O=Tree[o],LC=Tree[o<<1],RC=Tree[o<<1|1];
    merge(O,LC,RC);
}
void build_tree(int o,int L,int R){
    Node& O=Tree[o];
    O.L=L;
    O.R=R;
    if(L==R){
        O.maxP=O.maxS=O.ans=O.sum=A[L];
    }else{
        int M=L+(R-L)/2;
        build_tree(o<<1,L,M);
        build_tree(o<<1|1,M+1,R);
        maintain(o);
    }
}
void update(int o,int p,int v){
    Node& O=Tree[o];
    int& L=O.L,R=O.R;
    if(L==R){
        O.maxP=O.maxS=O.ans=O.sum=v;
    }else{
        int M=L+(R-L)/2;
        if(p<=M)
            update(o<<1,p,v);
        else
            update(o<<1|1,p,v);
        maintain(o);
    }
}
int ql,qr;
Node query(int o){
    Node& O=Tree[o];
    int& L=O.L,R=O.R;
    if(ql<=L && R<=qr){
        return Tree[o];
    }
    int M=L+(R-L)/2;
    Node ANS,LC,RC;
    if(ql<=M){
        LC=query(o<<1);
        if(qr>M){
            RC=query(o<<1|1);
            merge(ANS,LC,RC);
            return ANS;
        }else{
            return LC;
        }
    }else{
        RC=query(o<<1|1);
        return RC;
    }
}
int main(){
    int n,m;
    register int i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        scanf("%d",&A[i]);
    build_tree(1,1,n);
    int k,a,b;
    Node ans;
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&k,&a,&b);
        if(k&1){
            if(a>b)
                swap(a,b);
            ql=a;
            qr=b;
            ans=query(1);
            printf("%d\n",ans.ans);
        }else{
            update(1,a,b);
        }
    }
    return 0;
}