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

思路

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

当 $x = 0$ 时

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

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

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

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

当 $x > 0$ 时

$\operatorname{cmin}(l, r) = x$ 要求：补区间中不能出现任何小于 $x$ 的元素。
$\operatorname{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$ 的限制，分为两种情况：

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

由于 $\operatorname{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;
}

思路

当 x = 0 时

当 x > 0 时

时间复杂度

代码实现

当 $x = 0$ 时

当 $x > 0$ 时