题解：P17234 [Algo Beat Contest 017 C] 交互题

思路

令 $x=\mathrm{mex}(l,r)=\mathrm{cmin}(l,r)$。由于序列长度为 $n$，$x$ 的可能取值范围为 $[0,n]$。我们可以按 $x$ 的值进行分类讨论：

当 $x=0$ 时

• $\mathrm{mex}(l,r)=0$ 的充要条件是：子区间 $[l,r]$ 内不包含 $0$。
• $\mathrm{cmin}(l,r)=0$ 的充要条件是：补区间内包含至少一个 $0$。

为满足上面的条件，若原序列中存在 $0$，任何不包含 $0$ 的区间必然将所有的 $0$ 留在补区间中。

故可以通过将 $0$ 的出现位置作为分隔点，将原序列划分为若干个不含 $0$ 的连续段。每一段长度记为 $\mathrm{len}$，则该段对答案的贡献为 $\frac{\mathrm{len}(\mathrm{len}+1)}{2}$。

若序列中不存在 $0$，则不存在满足条件的区间，答案直接为 $0$。

当 $x>0$ 时

• $\mathrm{cmin}(l,r)=x$ 要求：补区间中不能出现任何小于 $x$ 的元素。
• $\mathrm{mex}(l,r)=x$ 要求：子区间 $[l,r]$ 必须包含所有的 $0,1,\dots ,x-1$，并且子区间 $[l,r]$ 内不能包含 $x$。

换言之，所有的 $0,1,\dots ,x-1$ 必须全部被包含在子区间 $[l,r]$ 内。同时，补区间必须至少包含一个 $x$。

综合以上约束，我们可以从小到大枚举 $x\ge 1$：

令 $L$ 为序列中所有 $0,1,\dots ,x-1$ 出现位置的最小值，$R$ 为所有 $0,1,\dots ,x-1$ 出现位置的最大值。

为了使 $[l,r]$ 包含所有的 $0,1,\dots ,x-1$，必须满足 $l\le L$ 且 $r\ge R$。也就是说，区间 $[l,r]$ 必须覆盖最小覆盖区间 $[L,R]$。

接下来考虑 $[l,r]$ 不能包含 $x$ 的限制，分为两种情况：

1. 区间 $[L,R]$ 内存在 $x$：由于 $[l,r]$ 必然覆盖 $[L,R]$，此时无论如何选择边界，区间内都会包含 $x$，没有满足条件的方案。

2. 区间 $[L,R]$ 内不存在 $x$：我们向两侧延伸，找到 $L$ 左侧第一个 $x$ 的位置（记为 $pl$），以及 $R$ 右侧第一个 $x$ 的位置（记为 $pr$）。为了不将外部的 $x$ 包入区间，$l$ 的合法取值范围为 $(pl,L]$，$r$ 的合法取值范围为 $[R,pr)$。

   特别地，若一侧不存在 $x$，则 $pl$ 视为 $0$，$pr$ 视为 $n+1$。满足边界条件的方案数即为 $(L-pl)\times (pr-R)$。

   由于 $\mathrm{cmin}(l,r)=x$ 要求补区间必须存在至少一个 $x$，若原序列中没有 $x$，则条件无法满足。

时间复杂度

预处理所有元素的出现位置为 $O(n)$。枚举 $x$ 的过程中，每次通过二分查找确定 $x$ 在 $[L,R]$ 两侧最近的出现位置，时间复杂度为 $O(\log n)$。

总时间复杂度为 $O(n\log n)$。

代码实现

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

const int N = 2e5 + 5;
int n, a[N];
vector<int> p[N];

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

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (a[i] < N)
        {
            p[a[i]].push_back(i);
        }
    }

    // 如果没有 0，答案必定为 0
    if (p[0].empty())
    {
        cout << "0\n";
        return 0;
    }

    long long ans = 0;

    // x = 0 的情况：统计被 0 分割的所有连续子段
    int last = 0;
    for (int k : p[0])
    {
        long long len = k - last - 1;
        ans += 1ll * len * (len + 1) / 2;
        last = k;
    }
    long long len = n - last;
    ans += len * (len + 1) / 2;

    // x > 0 的情况
    int L = n + 1, R = 0;
    for (int x = 1; x <= n; x++)
    {
        // 更新包含所有 0, 1, ..., x-1 的最小覆盖区间 [L, R]
        L = min(L, p[x - 1].front());
        R = max(R, p[x - 1].back());

        // 如果序列中不存在 x，则不可能满足 cmin = x，结束枚举
        if (p[x].empty())
            break;

        // 在 p[x] 中二分查找第一个大于等于 L 的位置
        auto it = lower_bound(p[x].begin(), p[x].end(), L);

        // 如果找到的 x 位置小于等于 R，说明区间 [L, R] 内包含 x，方案数为 0
        if (it != p[x].end() && *it <= R)
            continue;

        // 查找 L 左侧第一个 x 的位置 pl 和 R 右侧第一个 x 的位置 pr
        int pl = (it == p[x].begin()) ? 0 : *prev(it);
        int pr = (it == p[x].end()) ? n + 1 : *it;

        ans += 1ll * (L - pl) * (pr - R);
    }

    cout << ans << "\n";
    return 0;
}