题解：CF2185G Mixing MEXes

· · 题解

前言

数组开小调了两个小时。警示后人。

Description

给定 n 个数组 a_1, a_2, \ldots, a_n。

对这些数组恰好执行一次如下操作：

  • 在 a_1, a_2, \ldots, a_n 中任选一个数组。假设选择了 a_i（1 \leq i \leq n）。
  • 在该数组 a_i 内任选一个元素。假设选择了 a_i 的第 j 个元素，记为 a_{i,j}（1 \leq j \leq |a_i|，其中 |a_i| 表示数组 a_i 的长度）。
  • 在其它数组中选一个（不能是 a_i 本身）。假设选择了 a_k（1 \leq k \leq n, k \neq i）。
  • 将 a_{i,j} 加到数组 a_k 的末尾，并且从 a_i 中移除 a_{i,j}。
  • 本次操作 (i, j, k) 的价值定义为操作执行后所有数组的 \operatorname{MEX} 之和。更正式一点，操作后的价值为 \sum_{i=1}^{n} \operatorname{MEX}(a_i)。

计算所有可能的不同独立操作的价值之和。

Solution

处理出来每个序列的 \operatorname{MEX}。

发现只进行一次操作这个限制非常厉害。

因为数的总数很少，所以我们可以依次枚举每个数，计算挪走这个数对答案的贡献。

考虑把一个数 x 挪到另一个 \operatorname{MEX}\ne x 的序列中，则这次操作不会改变这个序列的 \operatorname{MEX}。

如果把 x 挪到一个 \operatorname{MEX}=x 的序列中，则这个序列的 \operatorname{MEX} 会变化。

而不难发现，因为至多加入一个元素，所以每个序列加入其 \operatorname{MEX} 后的新 \operatorname{MEX} 也是可以计算的。

我们就对这个东西开个桶记录一下总和就可以了，每个序列的新 \operatorname{MEX} 挂在原 \operatorname{MEX} 的位置上，额外记一个计数器表示 \operatorname{MEX}=x 的序列的数量。

Code

:::info[代码]

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
using namespace std;

int n;
vector<int> a[200010];

int pmex[200010],nd[200010];
int bkt[1000010];

long long mexcnt[1000010],ndsum[1000010];

int calcmex(vector<int> v){
    sort(v.begin(),v.end());
    int nowmex=0;
    for(int x:v){
        if(nowmex==x) nowmex++;
        else if(nowmex<x) break;
    }
    return nowmex;
}

int main(){
    cin.tie(0)->sync_with_stdio(false);

    int T;cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++){
            int l;cin>>l;
            a[i].resize(l);
            for(int &x:a[i]) cin>>x;
        }

        for(int p=1;p<=n;p++){
            pmex[p]=calcmex(a[p]);
            a[p].push_back(pmex[p]);
            nd[p]=calcmex(a[p]);
            a[p].pop_back();
        }

        long long mexsum=0;
        for(int p=1;p<=n;p++){
            mexsum+=pmex[p];
            mexcnt[pmex[p]]++;
            ndsum[pmex[p]]+=nd[p];
        }

        long long ans=0;
        for(int p=1;p<=n;p++){
            mexcnt[pmex[p]]--;
            ndsum[pmex[p]]-=nd[p];
            for(int x:a[p]) bkt[x]++;

            for(int x:a[p]){
                if(x<pmex[p]&&bkt[x]==1) mexsum-=pmex[p],mexsum+=x;

                ans+=1ll*(n-1)*mexsum;
                ans+=-1ll*mexcnt[x]*x+ndsum[x];

                if(x<pmex[p]&&bkt[x]==1) mexsum+=pmex[p],mexsum-=x;
            }

            mexcnt[pmex[p]]++;
            ndsum[pmex[p]]+=nd[p];
            for(int x:a[p]) bkt[x]--;
        }

        cout<<ans<<"\n";

        for(int p=1;p<=n;p++){
            a[p].clear();
            mexcnt[pmex[p]]--;
            ndsum[pmex[p]]-=nd[p];
            pmex[p]=nd[p]=0;
        }
    }

    # ifdef TakanashiHoshino
    cerr<<"\nUsed time: "<<clock()*1.0/CLOCKS_PER_SEC<<"s.\n";
    # endif
    return 0;
}

:::