题解：P17722 [SCP-S 2026] 档案 / file

RpUtl · 2026-10-20 14:58:08 · 题解

考虑把最终的贡献拆开。

首先对于第 i 个位置，在 m 次合并中，初始都会至少产生 i 的贡献，这部分的总贡献是 m\sum i。

考虑把第 j 个序列合并产生，对下标和产生的贡献，其是第 k 次合并，其中有 p_{j,t} 个 a_i 比 b_{j,t} 大，那么 b_{j,t} 会让这 p_{j,t} 个元素的下标都增加 1。则接下来会产生 (m-k+1)p_{j,t} 的贡献。

干脆直接处理出 w_j 表示把第 j 个序列合并产生的贡献，如果第 j 个序列在第 k 次被合并，产生的贡献是 (m-k+1)w_j。

相当于让 w_{1\sim m},1\sim m 匹配后相乘求和最小化贡献。直接排序即可。

求 p_{j,t} 直接二分，假设 n,m,L 同阶，复杂度做到 O(n\log n)。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
typedef long long ll;
int n, m, a[N], b[N];
ll ans, val[N];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m; 
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        ans += i;
    }
    sort(a + 1, a + 1 + n);
    ans *= m;
    for (int _ = 1, l; _ <= m; _++) {
        cin >> l; int x, p;
        for (int i = 1; i <= l; i++) {
            cin >> x;
            p = lower_bound(a + 1, a + 1 + n, x) - a;
            val[_] += n - p + 1; 
        }
    }
    sort(val + 1, val + 1 + m);
    for (int i = 1; i <= m; i++) {
        ans += val[i] * (m - i + 1);
    }
    cout << ans << '\n';
    return 0;
} 

如有错误，请指出。