CF2003D Turtle and a MEX Problem

题面

简化题意

给定 $n$ 个序列，你有一个数 $x$，你可以执行任意次（可以为零）如下操作：

• 选定一个数列，将 $x$ 变 $x$ 和次数列组成的序列的 $\mathrm{mex}$（最小的未出现的自然数）。

定义 $f(x)$ 为你的初始数字为 $x$ 时可以通过得到的最大值。求 $\sum_{i=0}^m f(i)$。

$n\leq 2\times 10^5$，序列长度和 $\leq2\times 10^5$，$m\leq 10^9$，值域 $\leq 10^9$。

EasyVersion：无特殊限制。

HardVersion：不能重复选择同一个数列。

题解

一个很显然的观察：将任意数字带入一个序列求 $\mathrm{mex}$ 时，只会有两种情况：

1. 得到的还是原来的数列的 $\mathrm{mex}$。
2. 当且仅当 $x$ 是原数列 $\mathrm{mex}$ 时发生，得到除了这个数之外的“次级 $\mathrm{mex}$”。

于是我们对于每个数列求出其 $\mathrm{mex}$ 和次级 $\mathrm{mex}$。令其为 $a,b$。于是任意 $\neq a$ 的数字跑一次这个操作会变成 $a$，等于 $a$ 的数字跑一次会变成 $b$，把数字转换关系连边。任意数连到 $a$ 不现实，只需要连一条有向边 $a\rightarrow b$ 即可。

然后你会得到一个非常美丽的有向图，显然 $b>a$，所以这个有向图是一个非常美丽的 DAG。现在考虑 EasyVersion，发现对于一个数 $x$，假设 $x$ 不属于任意的 $a$，就可以先随便丢到一个数列里变成某一个 $a$，然后沿着 $a\rightarrow b$ 的路线不断找到一个最大的 $b$。换句话说，我们只需要得到任意 $a$ 能得到的最大的 $b$，然后看看是 $x$ 更大还是 $b$ 更大就好了。对于等于某个 $a$ 的 $x$，依然可以先丢到其它数列里变成另外的 $a$，然后得到最大的 $b$。

于是，对于 EasyVersion，$f(x)$ 的计算方式就是比较 $x$ 和前面得到的最大的次级 $\mathrm{mex}$ 比较最大值。求 $\sum f(x)$ 也很好实现。

然后考虑 HardVersion。

注意到同样的数列不能用两次，现在假设有向图长这样：

然后假设我们有一个 $x = 2$，最优的方式是先通过 $3\rightarrow 5$ 这条边对应的数列变成 $3$，然后沿着 $3\rightarrow 4\rightarrow 6$ 变成 $6$。

假设这个图变成下面这样：

可以发现 $x=2$ 的最优方式就是通过 $4\rightarrow 6$ 这条边变成 $4$。

由上面的例子，不难发现：若存在一个点的出度 $\geq 2$，则任意数都可以先通过这个点的某一条边变成这个数，然后沿着其他的路径走到最大的数。也就是说，出度 $\geq 2$ 能到的最大的点，任意数都可以得到。或者，任意数都可以通过任意一条有向边 $a\rightarrow b$ 得到 $a$。于是，任意数能得到的最大的数就可以直接处理了。每个数能得到的最大的数可以建反图解决。

注意考虑不变的情况，实现上有一定的细节。

代码

以下是 HardVersion 的代码。

#include<bits/stdc++.h>
#define int long long
#ifdef DEBUG
#define debug(...) fprintf(stderr,__VA_ARGS__)
#else
#define debug
#endif
using namespace std;
bool Begin;
const int max_n=200005;
int read(){
    int x=0;bool w=0;char c=getchar();
    while(!isdigit(c)) w|=c=='-',c=getchar();
    while(isdigit(c)) x=x*10+(c^48),c=getchar();
    return w?-x:x;
}

int n,m;
vector<int> a;

int tot;
map<int,int> mp;

int ps[max_n];
int ID(int x){
    if(mp[x]) return mp[x];
    ++tot;
    mp[x]=tot;
    ps[tot]=x;
    return tot;
}

struct graph{
    int nx[max_n],ct,hd[max_n],to[max_n],deg[max_n];
    graph(){ct=0;}
    void clear(int n){
        for(int i=1;i<=n;++i)
            hd[i]=0,deg[i]=0;
        ct=0;
    }
    void add(int v,int u){
        ++deg[v];
        nx[++ct]=hd[u],hd[u]=ct,to[ct]=v;
    }
}e;
vector<int> L;
priority_queue<int> R;

int ed[max_n];
void dfs(int u,int num){
    ed[u]=num;
    for(int i=e.hd[u];i;i=e.nx[i]){
        int v=e.to[i];
        if(!ed[v])
            dfs(v,num);
    }
}

bool End;
#define File ""
signed main(void){
    #ifndef ONLINE_JUDGE
    freopen(File ".in","r",stdin),
    freopen(File ".out","w",stdout);
    #endif
    debug("Memory: %lf MB\n",(&Begin-&End)/1024.0/1024);
    for(int T=read();T;--T){
        n=read(),m=read();
        e.clear(tot);
        L.clear();
        for(int i=1;i<=tot;++i)
            ps[i]=0,ed[i]=0;
        mp.clear();tot=0;
        while(!R.empty()) R.pop();
        for(int i=0,_n;i<n;++i){
            _n=read();
            a.clear();
            a.emplace_back(-1);
            for(int j=0;j<_n;++j)
                a.emplace_back(read());
            sort(a.begin(),a.end());
            a.erase(unique(a.begin(),a.end()),a.end());
            a.emplace_back(1145141919810LL);
            _n=a.size();
            int l=-1,r=-1;
            for(int j=1;j<_n;++j)
                if(a[j]!=a[j-1]+1){
                    if(l==-1){
                        l=a[j-1]+1;
                        if(a[j]!=a[j-1]+2){
                            r=l+1;
                            break;
                        }
                    }
                    else{
                        r=a[j-1]+1;
                        break;
                    }
                }
            L.emplace_back(l);
            e.add(ID(l),ID(r));
            R.push(r);
        }
        sort(L.begin(),L.end());
        L.erase(unique(L.begin(),L.end()),L.end());
        while(!R.empty()){
            int st=mp[R.top()];R.pop();
            if(!ed[st])
                dfs(st,ps[st]);
        }
        int res=0,mx=-1;
        int _n=L.size();
        for(int i=0;i<_n;++i)
            mx=max(mx,L[i]);
        for(int i=1;i<=tot;++i) if(e.deg[i]>=2)
            mx=max(mx,ed[i]);
        int cnt=0;
        if(mx>m){
            for(int i=0;i<_n;++i) if(L[i]<=m){
                res+=max(mx,ed[mp[L[i]]]);
                ++cnt;
            }
            res+=(m+1-cnt)*mx;
        }
        else{
            for(int i=0;i<_n;++i) if(L[i]<=mx){
                res+=max(mx,ed[mp[L[i]]]);
                ++cnt;
            }
            res+=(mx+1-cnt)*mx;
            res+=(mx+1+m)*(m-(mx+1)+1)/2;
            for(int i=0;i<_n;++i) if(L[i]>mx && L[i]<=m)
                if(ed[mp[L[i]]]>L[i])
                    res=res-L[i]+ed[mp[L[i]]];
        }
        printf("%lld\n",res);
    }
    return 0;
}