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

梦见云月 · 2026-10-17 18:38:27 · 题解

考虑对于每个元素，我们只关心它前面会有哪些元素，排列，元素之间互相独立。

每加入一个元素，对于 a 中各个元素产生的贡献是可以预处理的。

对于 m 个数组，我们与先处理出它们的总贡献。

贪心的考虑是贡献小的在前面，非常显然。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int a[1000005];

struct node{
    int sum;
}e[1000005];
inline bool cmp(node x,node y){
    return x.sum<y.sum;
}
int ans;
int now;

signed 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];
        now+=i;
    }   
    sort(a+1,a+n+1);
    for (int i=1;i<=m;i++){
        int len;
        cin>>len;
        for (int j=1;j<=len;j++){
            int x;
            cin>>x;
            e[i].sum+=n-(upper_bound(a+1,a+n+1,x)-a)+1;
        }
    }
    sort(e+1,e+m+1,cmp);
    for (int i=1;i<=m;i++){
        now+=e[i].sum;
        ans+=now;
    }
    cout<<ans;
    return 0;
}