Solution. CF802N&O April Fools' Problem

Description

两个长度为 $n$ 的序列 $a_{1\dots n}$ 和 $b_{1\dots n}$，选择 $i_{1\dots k}$ 和 $j_{1\dots k}$，使得 $i_p\le j_p$，最小化 $\sum (a_{i_p}+b_{j_p})$。

Medium $1\le k\le n\le 2200$ 4s

Hard $1\le k\le n\le 500000$ 10s

Solution

对于这种限制+匹配，考虑网络流，容易想到的是让所有 $a_i$ 对 $b_j,j\ge i$ 连边，但这样边数是 $O(n^2)$（我感觉这样用 Primal Dual 也能过），我们可以通过如下建图将边数优化到 $O(n)$。

这里不需要细讲，很好理解，费用流即可求出答案，复杂度为 $O(nmf)=O(n^3)$，但是跑不满，如果用 Primal Dual 的复杂度是 $O(n^2\log n)$，Medium 到这里就做完了。

Hard 一种方法是用线段树模拟费用流，也就是优化费用流中每次找最短路的过程，也可以理解为一种反悔贪心，实现起来有一定困难，但是非常严谨且直观，思路也很连贯。

upd on 2023.1.16：修改了接下来的内容，给出了相对严谨和清晰的解释

另一种方法是，考虑 wqs 二分 + 反悔贪心。

这里 wqs 存在的意义是，让我们方便判断哪些决策需要进行，可以忽略 $k$ 的限制。

费用流模型每次增广的路径长度单调不降，至于为什么，考虑上一次的增广路径 $s\leadsto u\leadsto v\leadsto t$，假如我们想要使用 $v\leadsto u $ 的反向边，注意 $dis'(s,v)+dis'(u,t)\ge dis(s,v)+dis(u,t)$，算入反向边后，有 $dis'(s,t)\ge dis(s,t)$，这样就比较感性的完成了证明。

于是我们知道本题答案关于 $k$ 是下凸的，可以二分一个斜率，或者理解成给每次匹配一个额外的 cost。

接下来只需要贪心的选取能够为答案造成负贡献的匹配即可。

这里需要使用反悔贪心，具体的，从 $1$ 到 $n$ 遍历 $b_i$，对于每个 $b_i$ 选择最小的 $a_j,j\le i$ 匹配或者改良之前的一组匹配，后者即反悔操作。可以使用堆来维护所有的决策。

这样做实际上相当于逐步向网络中加点，不难发现网络中可能出现一条增广路径或者负环，也就对应了上述的两种决策，这样就证明了算法的正确性。

值得注意的是，我之前一直认为反悔决策只有增广路一种，但是这是平时使用 SSP 带来的错觉，负环也是一种反悔决策，尤其在 wqs + 反悔贪心中，因为这种套路基本都使用上述逐步向网络中加点的过程，这会导致曾经选择的增广路可能不优，从而产生负环。

有负环的网络流可以使用消圈算法或上下界网络流解决，应该是后者更加优秀。

Code

Primal Dual

#define int long long
namespace Main{
    const int N = 10005;
    const int inf = 0x3f3f3f3f3f3f3f3f;
    int tot, cnt, val[N<<1], dis[N], h[N], pnd[N], pid[N];
    bool vis[N];
    struct edge{
        int to, c, id;
        edge() {}
        edge(int to, int c, int id): to(to), c(c), id(id) {}
    };
    vector<edge> g[N];
    struct node{
        int u, dis;
        node() {}
        node(int u, int dis): u(u), dis(dis) {}
        bool operator < (const node &b) const {
            return dis > b.dis;
        }
    };
    void add(int u, int v, int w, int c){
        cnt++;
        g[u].emplace_back(v, c, cnt << 1);
        g[v].emplace_back(u, -c, cnt << 1 | 1);
        val[cnt<<1] = w;
        val[cnt<<1|1] = 0;
    }
    void spfa(int s){
        queue<int> q;
        memset(h, 0x3f, sizeof(h));
        memset(vis, 0, sizeof(vis));
        h[s] = 0, vis[s] = true;
        q.push(s);
        while(!q.empty()){
            int u = q.front(); q.pop();
            vis[u] = false;
            for(edge v: g[u]){
                if(val[v.id] && h[u] + v.c < h[v.to]){
                    h[v.to] = h[u] + v.c;
                    if(!vis[v.to]){
                        vis[v.to] = true;
                        q.push(v.to);
                    }
                }
            }
        }
    }
    bool dijkstra(int s, int t){
        priority_queue<node> q;
        memset(dis, 0x3f, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        dis[s] = 0;
        q.emplace(s, 0);
        while(!q.empty()){
            int u = q.top().u; q.pop();
            if(vis[u]) continue;
            vis[u] = true;
            for(edge v: g[u]){
                int w = h[u] - h[v.to] + v.c;
                if(val[v.id] && dis[u] + w < dis[v.to]){
                    dis[v.to] = dis[u] + w;
                    pnd[v.to] = u, pid[v.to] = v.id;
                    q.emplace(v.to, dis[v.to]);
                }
            }
        }
        return dis[t] != inf;
    }
    pair<int, int> mcmf(int s, int t){
        int minc = 0, maxf = 0;
        spfa(s);
        while(dijkstra(s, t)){
            int flow = inf;
            for(int i = 1; i <= tot; i++) h[i] += dis[i];
            for(int i = t; i != s; i = pnd[i]) flow = min(flow, val[pid[i]]);
            for(int i = t; i != s; i = pnd[i]) val[pid[i]] -= flow, val[pid[i]^1] += flow;
            maxf += flow;
            minc += flow * h[t];
        }
        return {minc, maxf};
    }
    int n, k, a[N], b[N];
    void Main(){
        input(n, k);
        for(int i = 0; i < n; i++) input(a[i]);
        for(int i = 0; i < n; i++) input(b[i]);
        for(int i = 0; i < n; i++) add(2 * n + 1, i + 1, 1, 0), add(i + 1, n + i + 1, 1, a[i] + b[i]), add(n + i + 1, 2 * n + 2, 1, 0);
        for(int i = 1; i < n; i++) add(n + i, n + i + 1, inf, b[i] - b[i-1]);
        add(2 * n + 3, 2 * n + 1, k, 0);
        tot = 2 * n + 3;
        pair<int, int> ans = mcmf(2 * n + 3, 2 * n + 2);
        assert(ans.second == k);
        write(ans.first);
        return;
    }
} // namespace
#undef int

wqs

#define int long long
namespace Main{
    const int N = 500005;
    int n, k, a[N], b[N];
    void Main(){
        input(n, k);
        for(int i = 0; i < n; i++) input(a[i]);
        for(int i = 0; i < n; i++) input(b[i]);
        int l = 0, r = 2e9;
        while(l <= r){
            int mid = l + r >> 1;
            int cnt = 0, val = 0;
            priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
            for(int i = 0; i < n; i++){
                q.emplace(a[i], 0);
                int tmp = q.top().first + b[i] - mid;
                if(tmp < 0){
                    val += tmp;
                    cnt += q.top().second == 0;
                    q.pop();
                    q.emplace(mid - b[i], 1);
                }
            }
            if(cnt == k){
                write(val + k * mid);
                return;
            }
            if(cnt > k) r = mid - 1;
            else l = mid + 1;
        }
        return;
    }
} // namespace

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。