题解：AT_abc363_g [ABC363G] Dynamic Scheduling

· · 题解

线段树分治 + 模拟费用流解法。

前置知识：线段树分治，费用流。

题意

题解

jiangly 讲课时讲了这道题，受益良多，遂以题解记之。

首先对于静态问题有一个经典贪心，把每个人物挂在时间 p_i 处，每个时刻都做时间后缀中剩下的收益最大的任务。

但是贪心显然不好改成在线。jiangly 的解法是考虑改成费用流，然后离线下来线段树分治去掉删除操作，用模拟费用流解决。

首先费用流是好改的，每个时刻开一个点向前连容量无限费用为 0 的边，每个点向汇点连容量为 1 费用为 0 的边，根据每个任务的参数从源点向 d_i 连容量为 1 费用为 p_i 的边，求最大费用最大流。这种费用流改成模拟费用流是比较经典的。

用线段树分治去掉删除操作后，考虑如何在网络流图上加边，加边后有三种可能：产生新的流，产生新的正环（显然求最大费用流时也有消圈定理），不对结果产生影响。

容易发现，任意时刻残量网络都形如时间轴上每个点向源汇点连若干条边（向汇点连的就是原先的边，向源点连的是流过后的反向边）。考虑如何新增一个流量（或者去掉一个正环），那么要么在时间轴上往前流找到一个费用最大的出边（可能是指向汇点的边或指向源点的反向边，前者流量 +1，后者解决正环），或者向后流若干条反向边找到费用最大的出边（同理）。

不妨设从某个点指向源汇的出边费用最大值为 x，那么第一种是简单的，就是从前缀 x 的最大值处流出（因为时间轴上的边容量无限可以随便流），但是第二种还要考虑反向边是否存在，这怎么办呢？

考虑设某一条边的反向边容量为 c，那么就是往后走若干条 c\ge 1 的边找到 x，即找到第一个 c=0 之前的 x 最大值。

容易发现这些都可以线段树维护，如果费用 p+x >0 就流一下，那么考虑一个流量会对网络流图产生什么影响。

首先向左流会使区间的 c 增加 1，向右流会使得区间的 c 减少 1。然后会用掉原有的一条出边并新增一条反向边。

乂？我们发现了一个问题：c 有区间加的操作，可能让区间内的 0 突然出现或消失，怎么维护第一个 0 之前 x 的最小值呢？

这是经典的，先在序列末尾新增一条 c 恒定为 0 的边，然后改为维护 c 的区间最小值之前 x 的最大值，这样 c 的区间加就不会对它产生影响，并且在后缀查询时和原问题是完全相同的。然后结点合并是简单的，不会可以参考代码实现。

注意一个点可能连多条反向边，需要用 std::multiset 在叶子处维护。

最后考虑线段树分治如何回退操作。每一层干的事情大致是若干个 c 的区间修改和 x 的单点修改，那么用一个栈把每一层的修改存下来，退出结点时反向做一遍就行了，因为每次操作只会对应 O(1) 的修改所以不会使复杂度变劣。

线段树分治中，每条流会被考虑 O(\log q) 次，每次复杂度 O(\log n)。于是复杂度 O(q\log q\log n)。

code

#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123=(e);i<=E123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123=(e);i>=E123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i64 read(){
    i64 x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const i64 N=1e5+5,inf=0x3f3f3f3f;
i64 n,q,d[N],p[N],pre[N],ans[N];
//pre 数组用来预处理每个任务影响的区间。
#define mid ((l+r)>>1)
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
struct Node{
    pii maxv,lmax;//区间最大值及其下标，第一个最小的 c 前的区间最大值及其下标。
    i64 minc;//区间 c 最小值。
    Node operator +(const Node &r){
        Node res;
        res.maxv=max(maxv,r.maxv);
        res.minc=min(minc,r.minc);
        if(res.minc==minc){
//如果当前结点 c 的最小值从左边继承过来则第一个最小的 c 在左边。
            res.lmax=lmax;
        }else{
//否则在右边。
            res.lmax=max(maxv,r.lmax);
        }
        return res;
    }
};//线段树结点信息及合并。
multiset<i64> ed[N];//存储结点所有出边的费用。
struct SegTree{
    Node info[N<<2];//结点信息。
    i64 mark[N<<2];//c 的区间修改的懒标记。
    void PushDown(i64 id){
        info[id<<1].minc+=mark[id];
        info[id<<1|1].minc+=mark[id];
        mark[id<<1]+=mark[id];
        mark[id<<1|1]+=mark[id];
        mark[id]=0;
    }
    void Build(i64 l=1,i64 r=n,i64 id=1){//初始化。
        mark[id]=0;
        if(l==r){
            ed[l].insert(0);
            info[id].maxv=info[id].lmax=mkp(0,l);
            return;
        }
        Build(lson);Build(rson);
        info[id]=info[id<<1]+info[id<<1|1];
    }
    void UpdateV(i64 P,i64 X,i64 l=1,i64 r=n,i64 id=1){//新增出边。
        if(l==r){
            ed[l].insert(X);
            info[id].maxv=info[id].lmax=mkp(*prev(ed[l].end()),l);
            return;
        }
        if(mark[id]) PushDown(id);
        if(P<=mid) UpdateV(P,X,lson);
        else       UpdateV(P,X,rson);
        info[id]=info[id<<1]+info[id<<1|1];
    }
    void EraseV(i64 P,i64 X,i64 l=1,i64 r=n,i64 id=1){//删除出边。
        if(l==r){
            ed[l].erase(ed[l].find(X));
            info[id].maxv=info[id].lmax=mkp(-inf,l);
            if(ed[l].size()) info[id].maxv=info[id].lmax=mkp(*prev(ed[l].end()),l);
            return;
        }
        if(mark[id]) PushDown(id);
        if(P<=mid) EraseV(P,X,lson);
        else       EraseV(P,X,rson);
        info[id]=info[id<<1]+info[id<<1|1];
    }
    void Modify(i64 L,i64 R,i64 X,i64 l=1,i64 r=n,i64 id=1){//c 的区间加。
        if(L>R) return;
        if(L<=l&&r<=R){
            info[id].minc+=X;
            mark[id]+=X;
            return;
        }
        if(mark[id]) PushDown(id);
        if(L<=mid) Modify(L,R,X,lson);
        if(mid< R) Modify(L,R,X,rson);
        info[id]=info[id<<1]+info[id<<1|1];
    }
    Node Query(i64 L,i64 R,i64 l=1,i64 r=n,i64 id=1){//查询，注意信息如何合并。
        if(L>R){
            return Node{mkp(-inf,-1),mkp(-inf,-1),0};
        }
        if(L<=l&&r<=R){
            return info[id];
        }
        if(mark[id]) PushDown(id);
        if(R<=mid){
            return Query(L,R,lson);
        }else if(mid<L){
            return Query(L,R,rson);
        }else{
            return Query(L,R,lson)+Query(L,R,rson);
        }
    }
}mt;
vector<pii> node[N<<2];
void Update(i64 L,i64 R,i64 D,i64 P,i64 l=0,i64 r=q,i64 id=1){//线段树分治部分，将问题扔到时间轴上。
    if(L<=l&&r<=R){
        node[id].push_back(mkp(D,P));
        return;
    }
    if(L<=mid) Update(L,R,D,P,lson);
    if(mid< R) Update(L,R,D,P,rson);
}
i64 ncost;
struct oper{//存储操作方便回退。
    i64 l,r,v;
};
void solve(i64 l=0,i64 r=q,i64 id=1){//线段树分治，处理问题。
    stack<oper> sv;
    i64 add=0;
    for(auto op:node[id]){
        i64 d=op.fi,p=op.se;
        pii lmx=mt.Query(1,d).maxv,rmx=mt.Query(d,n).lmax;
        if(lmx>=rmx){//走较大的那边。
            if(p+lmx.fi>0){//如果不是正环且不增加流量则不增广。
                ncost+=p+lmx.fi;
                add+=p+lmx.fi;
                mt.EraseV(lmx.se,lmx.fi);
                sv.push(oper{-2,lmx.se,lmx.fi});
                mt.UpdateV(d,-p);
                sv.push(oper{-1,d,-p});
                mt.Modify(lmx.se,d-1,1);
                sv.push(oper{lmx.se,d-1,1});
            }
        }else{
            if(p+rmx.fi>0){
                ncost+=p+rmx.fi;
                add+=p+rmx.fi;
                mt.EraseV(rmx.se,rmx.fi);
                sv.push(oper{-2,rmx.se,rmx.fi});
                mt.UpdateV(d,-p);
                sv.push(oper{-1,d,-p});
                mt.Modify(d,rmx.se-1,-1);
                sv.push(oper{d,rmx.se-1,-1});
            }
        }
    }
    if(l==r){
        ans[l]=ncost;
    }else{
        solve(lson);solve(rson);
    }
    while(sv.size()){//回退操作
        oper i=sv.top();sv.pop();
        if(i.l==-1){
            mt.EraseV(i.r,i.v);
        }else if(i.l==-2){
            mt.UpdateV(i.r,i.v);
        }else{
            mt.Modify(i.l,i.r,-i.v);
        }
    }
    ncost-=add;
}
#undef mid
#undef lson
#undef rson
signed main(){
    n=read();q=read();
    forup(i,1,n) d[i]=read();
    forup(i,1,n) p[i]=read();
    forup(i,1,q){//预处理每个任务影响的区间。
        i64 c=read(),x=read(),y=read();
        Update(pre[c],i-1,d[c],p[c]);
        pre[c]=i;d[c]=x;p[c]=y;
    }
    forup(i,1,n){
        Update(pre[i],q,d[i],p[i]);
    }
    mt.Build();//记得建树。
    solve();
    forup(i,1,q){
        printf("%lld\n",ans[i]);
    }
}