k-Maximum Subsequence Sum 题解

大眼仔Happy · 2023-10-06 22:24:29 · 个人记录

题目传送门

模拟赛的题搞了这个算法，于是来找点题做了一下。

模拟费用流的好题！！！

讲到费用流，我们先考虑一下这道题如果用费用流应该怎么做？

首先先构建一个费用流的模型：S\xrightarrow{\text{flow}=1,\text{cost=0}} i\xrightarrow{\text{flow}=1,\text{cost=0}}T，i\xrightarrow{\text{flow}=\inf,\text{cost=}a_i}i+1，其中 S,T 都有 k 的流量（即只能选择 k 个区间）。考虑增广路 S\to L\to R\to T 的含义：即表示选择了 [L,R-1] 这一段。每次增广就是（贪心）选择新的最大的区间，或者对前面的选择反悔。

而由于网络流本身就具有反悔的性质（即反向边），所以实际上就是反悔贪心。（引用一句话：反悔贪心需要证明，而费用流的正确性大家都默认了）

所以我们就得到了一个结论：

每次取出最大的连续子段和，目前答案加上这个子段和，然后再把这个子段取相反数（相当于反向边），然后求整个过程答案的最大值。

图肯定是不能建出来的，但是可以用线段树维护（还挺难打），时间复杂度 O(nk\log n)。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
#define ll long long
ll inline read()
{
    ll num=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){num=(num<<3)+(num<<1)+(ch^48);ch=getchar();}
    return num*f;
}
int n,q;
ll s,ans,a[N];
struct node{int l,r;ll w;};
struct data
{
    ll sum;
    node lmx,rmx,mx;
    node lmn,rmn,mn;
    data friend operator +(const data A,const data B)
    {
        data res;

        res.sum=A.sum+B.sum;

        if(A.lmx.w>A.sum+B.lmx.w)res.lmx=A.lmx;
        else res.lmx=(node){A.lmx.l,B.lmx.r,A.sum+B.lmx.w};
        if(B.rmx.w>B.sum+A.rmx.w)res.rmx=B.rmx;
        else res.rmx=(node){A.rmx.l,B.rmx.r,B.sum+A.rmx.w};
        res.mx=(node){A.rmx.l,B.lmx.r,A.rmx.w+B.lmx.w};
        if(res.mx.w<A.mx.w)res.mx=A.mx;
        if(res.mx.w<B.mx.w)res.mx=B.mx;

        if(A.lmn.w<A.sum+B.lmn.w)res.lmn=A.lmn;
        else res.lmn=(node){A.lmn.l,B.lmn.r,A.sum+B.lmn.w};
        if(B.rmn.w<B.sum+A.rmn.w)res.rmn=B.rmn;
        else res.rmn=(node){A.rmn.l,B.rmn.r,B.sum+A.rmn.w};
        res.mn=(node){A.rmn.l,B.lmn.r,A.rmn.w+B.lmn.w};
        if(res.mn.w>A.mn.w)res.mn=A.mn;
        if(res.mn.w>B.mn.w)res.mn=B.mn;

        return res;
    } 
};
struct Segment_Tree
{
    data t[N<<2];bool tag[N<<2];
    void up(int k){t[k]=t[k<<1]+t[k<<1|1];}
    void build(int k,int l,int r)
    {
        if(l==r)
        {
            t[k].sum=a[l];
            t[k].lmx=t[k].rmx=t[k].mx=(node){l,l,a[l]};
            t[k].lmn=t[k].rmn=t[k].mn=(node){l,l,a[l]};
            return;
        }
        int mid=l+r>>1;
        build(k<<1,l,mid);
        build(k<<1|1,mid+1,r);
        up(k);
    }
    void LT(int k,int l,int r)
    {
        t[k].sum=-t[k].sum;

        swap(t[k].lmx,t[k].lmn);
        t[k].lmx.w=-t[k].lmx.w;
        t[k].lmn.w=-t[k].lmn.w;

        swap(t[k].rmx,t[k].rmn);
        t[k].rmx.w=-t[k].rmx.w;
        t[k].rmn.w=-t[k].rmn.w;

        swap(t[k].mx,t[k].mn);
        t[k].mx.w=-t[k].mx.w;
        t[k].mn.w=-t[k].mn.w;

        tag[k]^=1;
    }
    void down(int k,int l,int r)
    {
        if(!tag[k])return;
        int mid=l+r>>1;
        LT(k<<1,l,mid);
        LT(k<<1|1,mid+1,r);
        tag[k]=0;
    }
    void upd(int k,int l,int r,int q,ll v)
    {
        if(l==r)
        {
            t[k].sum=v;
            t[k].lmx=t[k].rmx=t[k].mx=(node){l,l,v};
            t[k].lmn=t[k].rmn=t[k].mn=(node){l,l,v};
            return;
        }
        down(k,l,r);
        int mid=l+r>>1;
        if(q<=mid)upd(k<<1,l,mid,q,v);
        else upd(k<<1|1,mid+1,r,q,v);
        up(k);
    }
    void rev(int k,int l,int r,int ql,int qr)
    {
        if(ql<=l&&r<=qr){LT(k,l,r);return;}
        int mid=l+r>>1;
        down(k,l,r);
        if(ql<=mid)rev(k<<1,l,mid,ql,qr);
        if(qr>mid)rev(k<<1|1,mid+1,r,ql,qr);
        up(k);
    }
    data ask(int k,int l,int r,int ql,int qr)
    {
        if(ql<=l&&r<=qr)return t[k];
        down(k,l,r);
        int mid=l+r>>1;
        if(ql<=mid&&qr>mid)return ask(k<<1,l,mid,ql,qr)+ask(k<<1|1,mid+1,r,ql,qr);
        if(ql<=mid)return ask(k<<1,l,mid,ql,qr);
        if(qr>mid)return ask(k<<1|1,mid+1,r,ql,qr);
    } 
}Tree;
stack<node>sta;
void solve(int l,int r,int k)
{
    ans=0;
    for(int i=1;i<=k;i++)
    {
        node d=Tree.ask(1,1,n,l,r).mx;
        if(d.w<=0)break;
        ans+=d.w;
        Tree.rev(1,1,n,d.l,d.r);
        sta.push(d);
    }
    while(!sta.empty())
    {
        node d=sta.top();sta.pop();
        Tree.rev(1,1,n,d.l,d.r);
    }
    printf("%lld\n",ans);
}
int main(){
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    Tree.build(1,1,n);
    q=read();
    while(q--)
    {
        int op=read();
        if(op==0)
        {
            int x=read();ll v=read();
            Tree.upd(1,1,n,x,v);
        }
        else 
        {
            int l,r,k;
            l=read();r=read();k=read();
            solve(l,r,k);
        }
    }
    return 0;
}