洛谷P5470 [NOI2019] 序列题解

题目链接：P5470 [NOI2019] 序列

题意：

给定两个长度为 \(n\) 的正整数序列 \(\{a_i\}\) 与 \(\{b_i\}\)，序列的下标为 \(1, 2, \cdots , n\)。

现在你需要分别对两个序列各指定恰好 \(K\) 个下标，共 \(2K\) 个下标

要求至少有 \(L\) 个下标在两个序列中都被指定，使得这 \(2K\) 个下标在序列中对应的元素的总和最大。

形式化地说，你需要确定两个长度为 \(K\) 的序列 \(\{c_i\}, \{d_i\}\)，其中 \[ 1 \leq c_1 < c_2 < \cdots < c_K \leq n , 1 \leq d_1 < d_2 < \cdots < d_K \leq n \] 并要求 \(\{c_1, c_2, \cdots , c_K\} \cap \{d_1, d_2, · · · , d_K\}\geq L\) ，目标是最大化 \(\sum^{K}_{i=1} a_{c_i} +\sum^{K}_{i=1} b_{d_i}\) 。

输入格式：

本题输入文件包含多组数据。

第一行一个正整数 \(T\) 表示数据组数。接下来每三行表示一组数据。

每组数据第一行三个整数 \(n, K, L\)，变量意义见题目描述。

每组数据第二行 \(n\) 个整数表示序列 \(\{a_i\}\)。

每组数据第三行 \(n\) 个整数表示序列 \(\{b_i\}\)。

输出格式：

对于每组数据输出一行一个整数表示答案。

数据范围：

\(1\le T \leq 10 , 1 \leq \sum n \leq 10^6, 1 \leq L \leq K \leq n \leq 2 \times 10^5, 1 \leq a_i, b_i \leq 10^9\)。

建议先做一下 CF436E Cardboard Box ，这道题相当于那题的加强版。

注意到如果 \(L\) 个公共部分已经确定时，直接选 \(K-L\) 个最大的就是最优的。

那么我们直接选 \(K\) 个最大的，然后用反悔贪心每次多选一个公共部分，直到变成 \(L\) 个。

考虑每次决策如何增加公共部分：

找一个选了的 \(a_i\) 和一个选了的 \(b_j\) ，用 \(b_i\) 代替 \(b_j\) ，花费 \(b_i - b_j\) 。
找一个选了的 \(b_i\) 和一个选了的 \(a_j\) ，用 \(a_i\) 代替 \(a_j\) ，花费 \(a_i - a_j\) 。
找一个选了的 \(a_i\) 和一个选了的 \(b_j\) ，再找一个没选的位置 \(k\) ，替换为 \(a_k\) 和 \(b_k\) ，花费 \(a_k + b_k - a_i - b_j\) 。
找一个选了的 \(a_i\) 和一个选了的 \(b_j\) ，再找一个都选了的位置 \(k\) ，用 \(a_j\) 和 \(b_i\) 替换 \(a_k\) 和 \(b_k\) ，

注意这里是用 \(a_j\) 和 \(b_i\) ，这样 \(a_j,b_j\) 和 \(a_i,b_i\) 就是公共的部分，花费为 \(a_j + b_i - a_k - b_k\) 。

那么我们用 6 个大根堆维护 \((a_i),\ (-a_i),\ (b_i), \ (-b_i),\ (a_i + b_i), \ (-a_i - b_i)\) 即可。

时间复杂度 \(\mathcal{O}(N \log N)\) ，其中 \(N = \sum n\) 。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define mem(a) memset(a, 0, sizeof(a))
#define N ((int)(2e5 + 15))

int n, type[N];
struct node { int x, i; } a[N], b[N];
bool operator<(const node &x, const node &y) { return x.x > y.x; }
bool operator>(const node &x, const node &y) { return x.x < y.x; }
struct qwq
{
    int op; priority_queue< node, vector<node>, greater<node> > q;
    void up(){ while(!q.empty() && type[q.top().i] != op) q.pop(); }
    void push(const node &x) { q.push(x); }
    node top() { up(); return q.top(); }
    bool empty() { up(); return q.empty(); }
    void clear() { op = 0; q = {}; }
} q1, q2, q3, q4, q5, q6;
void clear()
{
    rep(i, 0, n + 5) type[i] = 0;
    q1.clear(); q2.clear(); q3.clear(); q4.clear(); q5.clear(); q6.clear();
}
void solve()
{
    clear(); int K, L, res = 0; cin >> n >> K >> L;
    rep(i, 1, n) { cin >> a[i].x; a[i].i = i; }
    rep(i, 1, n) { cin >> b[i].x; b[i].i = i; }
    sort(a + 1, a + 1 + n); sort(b + 1, b + 1 + n);
    rep(i, 1, K) { res += a[i].x, type[a[i].i] = 1; }
    rep(i, 1, K) { res += b[i].x, type[b[i].i] += 2; }
    int cnt = 0; rep(i, 1, n) if(type[i] == 3) ++cnt;
    static const auto cmp = [&](node x, node y) { return x.i < y.i; };
    sort(a + 1, a + 1 + n, cmp); sort(b + 1, b + 1 + n, cmp);
    q1.op = 2; q2.op = 1; q3.op = 1; q4.op = 2; q5.op = 0; q6.op = 3;
    rep(i, 1, n)
    {
        q1.push({a[i].x, i}); q2.push({-a[i].x, i});
        q3.push({b[i].x, i}); q4.push({-b[i].x, i});
        q5.push({a[i].x + b[i].x, i}); q6.push({-a[i].x - b[i].x, i});
    }
    rep(awa, 1, L - cnt)
    {
        int x, i, j, k, op = -1, mx = -INF;
        if(!q3.empty() && !q4.empty() && (x = b[q3.top().i].x - b[q4.top().i].x) > mx) { mx = x; i = q3.top().i; j = q4.top().i; op = 1; }
        if(!q1.empty() && !q2.empty() && (x = a[q1.top().i].x - a[q2.top().i].x) > mx) { mx = x; i = q1.top().i; j = q2.top().i; op = 2; }
        if(!q5.empty() && !q4.empty() && !q2.empty())
            if((x = a[q5.top().i].x + b[q5.top().i].x - a[q2.top().i].x - b[q4.top().i].x) > mx)
                { mx = x; i = q2.top().i; j = q4.top().i; k = q5.top().i; op = 3; }
        if(!q6.empty() && !q3.empty() && !q1.empty())
            if((x = a[q1.top().i].x + b[q3.top().i].x - a[q6.top().i].x - b[q6.top().i].x) > mx)
                { mx = x; i = q3.top().i; j = q1.top().i; k = q6.top().i; op = 4; }
        res += mx; if(op == -1) assert(0);
        else if(op == 1) { type[i] = 3; type[j] = 0; q6.push({-a[i].x - b[i].x, i}); q5.push({a[j].x + b[j].x, j}); }
        else if(op == 2) { type[i] = 3; type[j] = 0; q6.push({-a[i].x - b[i].x, i}); q5.push({a[j].x + b[j].x, j}); }
        else if(op == 3) { type[k] = 3; type[i] = type[j] = 0; q6.push({-a[k].x - b[k].x, k}); q5.push({a[i].x + b[i].x, i}); q5.push({a[j].x + b[j].x, j}); }
        else if(op == 4) { type[k] = 0; type[i] = type[j] = 3; q5.push({a[k].x + b[k].x, k}); q6.push({-a[i].x - b[i].x, i}); q6.push({-a[j].x - b[j].x, j}); }
    }
    cout << res << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}