P17722 [SCP-S 2026] 档案 / file
赛时是感性理解乱写通过的。
大概就是，考虑你已经有一个排列，怎么算答案。设 \(f_i\) 表示 \(a_1 \sim a_n\) 比第 \(i\) 个序列大的数的个数，那么插入 \(i\) 产生 \(f_i\) 的偏移，答案就是 \(f\) 的前缀和之和。
显然将 \(f\) 升序排序最优。注意加上初始下标的贡献。
const int N = 2e6 + 5;
int n, m, a[N]; i64 f[N];void _main() {cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i];sort(a + 1, a + n + 1);for (int i = 1, x; i <= m; i++) {cin >> x;for (int j = 0, v; j < x; j++) {cin >> v;f[i] += n + 1 - (upper_bound(a + 1, a + n + 1, v) - a);}}i64 res = 0;sort(f + 1, f + m + 1);for (int i = 1; i <= m; i++) f[i] += f[i-1], res += f[i];res += 1LL * n*(n+1) / 2 * m;cout << res;
}