CF2003D2 Turtle and a MEX Problem (Hard Version)

传送门

Solution

设第 $i$ 个序列最小没出现的非负整数为 $v_i$，次小没出现的非负整数为 $u_i$。从 $u_i$ 向 $v_i$ 连有向边。由于 $u_i>v_i$，最后得到的是一张有向无环图，且每个点之间不一定连通。

设 $f_v$ 为能到达 $v$ 的点的最大值。 所有 $f_v$ 可通过拓扑排序 dp 求出。

令 $x=\max\{u_i\}$。设 $V$ 为所有入度大于 $1$ 的点的集合且 $v \in V$，令 $y=\max\{f_{u_i}\}$。则 $f(k)=\max\{x,y,f_k,k\}$。

$\max$ 中第一项为 $k$ 与 $v_i$ 最大的一个序列进行一次操作。

第二项为对 $k\neq v_{i_1}$ 的序列 $i_1$ 进行第一次操作，使 $k=v_{i_1}$，然后再与 $v_{i_1}=v_{i_2}$ 的序列 $i_2$ 进行第二次操作。

第三项为对 $k=v_i$ 的序列 $i$ 进行一次操作。

第四项为不进行任何操作。

当 $k\le \max\{x,y\}$ 时逐个计算 $f(k)$，当 $k>\max\{x,y\}$ 时，$f(k)=k$，此时直接等差数列求和得解。

时间复杂度 $O(\sum l_i)$

Code

注意点的序号可能会很大，选择离散化对点进行标号。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 2e5 + 10;

ll T, n, a[N], m, len, id_cnt, max_u, ans, max_v, idx[N], maxn[N], id[N], in[N], vis[N], ini[N];
queue<ll> q;
vector<ll> g[N << 2];

void dp()
{
    while (q.size()) {
        ll u = q.front(); q.pop();
        for (ll v : g[u]) {
            maxn[v] = max(maxn[v], maxn[u]);
            --in[v];
            if (!in[v]) 
                q.push(v);
        }
    }
}

void solve()
{
    for (int i = 1; i <= id_cnt; i++) {
        maxn[i] = in[i] = id[idx[i]] = ini[i] = 0;
        vector<ll>().swap(g[i]);
    }
    id_cnt = 0; max_u = 0; ans = 0; max_v = 0;
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &len);
        ll cnt = 0, u = -1, v = -1;
        for (int j = 0; j <= len + 2; j++)
            vis[j] = 0;
        for (int j = 1; j <= len; j++) {
            scanf("%lld", &a[j]);
            if (a[j] <= len + 2)
                vis[a[j]] = 1;
        }
        for (int j = 0; j <= len + 2; j++) {
            if (vis[j] == 0) {
                ++cnt;
                if (cnt == 1) u = j;
                else if (cnt == 2) {
                    v = j;
                    break;
                }
            }
        }
        if (!id[u]) id[u] = ++id_cnt, idx[id_cnt] = u;
        if (!id[v]) id[v] = ++id_cnt, idx[id_cnt] = v;
        g[id[v]].push_back(id[u]);
        in[id[u]]++; ini[id[u]]++;
        max_u = max(max_u, u);
    }
    for (int i = 1; i <= id_cnt; i++)
        if (!in[i]) {
            q.push(i);
            maxn[i] = idx[i];
        }    
    dp();
    for (int i = 1; i <= id_cnt; i++)
        if (ini[i] > 1)
            max_v = max(max_v, maxn[i]);
    for (int i = 0; i <= min(max(max_u, max_v), m); i++)
        ans += max(maxn[id[i]], max(max_u, max_v));
    if (max(max_u, max_v) < m)
        ans += (m - max(max_u, max_v)) * (m + max(max_u, max_v) + 1) / 2;
    printf("%lld\n", ans);
}

int main()
{
    scanf("%lld", &T);
    while (T--) solve();
    return 0;
}