【Codeforces 280D】k-Maximum Subsequence Sum

mrsrz 11月 29, 2019

线段树+堆，贪心或模拟费用流

题目大意：

给定一个数列，要支持以下操作：

单点修改。
给定区间，要选取不超过 $k$ 个（可以是 $0$ 个）不相交的子区间，使得这些子区间的和最大。求最大的和。

题解：

这题我一开始是按照贪心的思想写的（~~也不管什么证明感性理解觉得是对的就好了~~），写完以后再一想，发现的确和费用流干的事情很像，也就是所谓模拟费用流。

做法就是，每次贪心选择区间里的和最大的子段，然后原区间就被分成了左中右三块。对于左右两块，我们还可以去其和最大的子段。对于中间选的这块，我们可以通过删掉一个贡献为负的子段得到更大的贡献（相当于把原来选的区间分成两部分）。

那需要对这三个区间再做相同的子问题。每次要选取最大的，使用堆即可。

实际上，如果用费用流做这个问题，那么连边的方法是这样的：

源点向每个点、每个点向汇点连费用 $0$ 的边。

每个点向下一个点连容量 $1$ ，费用为数值大小的边，保证每个点最多选一次。最后可以加一个哨兵结点。

那么对于询问，就是把这张图的一个子图拿出来跑费用流，每流 $1$ 的流量相当于选了一个区间。

跑最大费用流即可。这个费用流算法显然是没问题的。

那么上面的贪心的做法中，我们每次贪心选择一个最大的区间，相当于费用流中找到一条最优的增广路进行增广。而那个取取反后的最大区间的操作，相当于费用流中的退流。

所以我们其实是通过高效的方法在模拟这个费用流。所以“贪心”是正确的。

所以只需要用线段树分别维护原序列和取反序列的区间最大子段和就好了。

这里由于要记录具体的区间，所以合并信息的时候稍微有些麻烦。

时间复杂度 $O(nk\log n)$ 。

Code：

#include<iostream>
#include<queue>
#include<algorithm>
#include<utility>
using namespace std;
const int N=1e5+5;
int n,m;
struct info{
    int L,R,l,r,val;bool tag;
    inline bool operator<(const info&rhs)const{return val<rhs.val;}
};
priority_queue<info>q;
struct data{
    pair<int,int>pre,suf;
    int mx,mxL,mxR;
    int L,R;
    int sum;
    inline void init(int x,int p){
        L=R=p;
        sum=x;
        pre=suf=make_pair(mx=x,mxL=mxR=p);
    }
    inline data operator+(const data&r)const{
        data ret;
        ret.sum=sum+r.sum;
        ret.L=L,ret.R=r.R;
        if(pre.first<sum+r.pre.first)ret.pre=make_pair(sum+r.pre.first,r.pre.second);
        else ret.pre=pre;
        if(r.suf.first<r.sum+suf.first)ret.suf=make_pair(r.sum+suf.first,suf.second);
        else ret.suf=r.suf;
        if(mx>r.mx)ret.mx=mx,ret.mxL=mxL,ret.mxR=mxR;else
        ret.mx=r.mx,ret.mxL=r.mxL,ret.mxR=r.mxR;
        if(suf.first+r.pre.first>ret.mx)
        ret.mx=suf.first+r.pre.first,ret.mxL=suf.second,ret.mxR=r.pre.second;
        return ret;
    }
}d[N<<2],_d[N<<2];
void build(int l,int r,int o){
    if(l==r){
        int x;
        cin>>x;
        d[o].init(x,l);
        _d[o].init(-x,l);
    }else{
        const int mid=l+r>>1;
        build(l,mid,o<<1),build(mid+1,r,o<<1|1);
        d[o]=d[o<<1]+d[o<<1|1];
        _d[o]=_d[o<<1]+_d[o<<1|1];
    }
}
void modify(int l,int r,int o,const int&pos,const int&v){
    if(l==r)d[o].init(v,l),_d[o].init(-v,l);else{
        const int mid=l+r>>1;
        if(pos<=mid)modify(l,mid,o<<1,pos,v);else modify(mid+1,r,o<<1|1,pos,v);
        d[o]=d[o<<1]+d[o<<1|1];
        _d[o]=_d[o<<1]+_d[o<<1|1];
    }
}
data query(int l,int r,int o,const int&L,const int&R,const bool&tag){
    if(L<=l&&r<=R)return(tag?_d[o]:d[o]);
    const int mid=l+r>>1;
    if(L<=mid&&mid<R)return query(l,mid,o<<1,L,R,tag)+query(mid+1,r,o<<1|1,L,R,tag);
    if(L<=mid)return query(l,mid,o<<1,L,R,tag);return query(mid+1,r,o<<1|1,L,R,tag);
}
void put(int L,int R,int l,int r,bool tg){
    if(L<=l-1){
        int L_=L,R_=l-1;
        data _=query(1,n,1,L_,R_,tg);
        if(_.mx>0)q.push((info){L_,R_,_.mxL,_.mxR,_.mx,tg});
    }
    if(r+1<=R){
        int L_=r+1,R_=R;
        data _=query(1,n,1,L_,R_,tg);
        if(_.mx>0)q.push((info){L_,R_,_.mxL,_.mxR,_.mx,tg});
    }
    data _=query(1,n,1,l,r,!tg);
    if(_.mx>0)q.push((info){l,r,_.mxL,_.mxR,_.mx,!tg});
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    build(1,n,1);
    for(cin>>m;m--;){
        int op;
        cin>>op;
        if(op){
            int l,r,k;
            cin>>l>>r>>k;
            data _=query(1,n,1,l,r,0);
            if(_.mx<0){
                cout<<"0\n";
                continue;
            }
            int ans=_.mx;
            while(!q.empty())q.pop();
            put(l,r,_.mxL,_.mxR,0);
            while(--k){
                if(q.empty())break;
                info _=q.top();
                q.pop();
                ans+=_.val;
                put(_.L,_.R,_.l,_.r,_.tag);
            }
            cout<<ans<<'\n';
        }else{
            int x,y;
            cin>>x>>y;
            modify(1,n,1,x,y);
        }
    }
    return 0;
}

Gitalking ...