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

· · 题解

0x00 前言

蒟蒻的痛。想了两小时有馀，我须省我是杂鱼！

0x01 解题思路

转化一下题面意思。

所以一个区间的 $\operatorname{mex}$ 为 $x$ 的充分必要条件是 $0\sim x-1$ 的数在 $a_l\dots a_r$ 均有出现，但 $x$ 在 $a_l\dots a_r$ 不出现。 $\operatorname{cmin}(l, r)$ 是 $a_1\dots a_{l-1}, a_{r + 1}\dots a_n$ 中出现的最小非负整数。 如果 $\operatorname{cmin}(l, r) = x$，那么 $a_1\dots a_{l-1}, a_{r + 1}\dots a_n$ 中所有数均大于等于 $x$，并且有 $x$ 出现。 所以**所有小于 $x$ 的数必然都被包含在了 $(l, r)$ 中**。 这个条件很好推，一个前缀最小值和后缀最小值推出来 $L_x$ 和 $R_x$。分别表示第一个比 $x$ 小的数的位置和最后一个比 $x$ 大的数的位置。 即 $L_x=\{i|a_i<x\}_{\min}, R_x=\{i|a_i<x\}_{\max}

Therefore \operatorname{cmin} 为 x 的区间一定包含 a_{L_x} \dots a_{R_x}

然后考虑猫耳小(mex)的 x\not\in a_l\dots a_r 限制，这说明对于所有 a_{pos_{x,i}}=x，这些 pos_{x, i} 把整个 a 切割成了若干段，那么合法的区间一定在其中的一段里。

设 \_l=pos_{x\,max} < L_x, \_r=pos_{x\,min} > R_x，没有符合条件的 pos_{x, i} 则 fallback 到 0 和 n + 1。因为是开区间，合法区间去不到 \_l,\_r。

Therefore 合法区间 l\in(\_l,L_x],r\in[R_x,\_r)

那么两式均为 x 对答案的贡献就是 (L_x-\_l)(\_r-R_x)。

但是我们不能忘掉，猫耳小为 x 还要求 0\sim x-1 的出现。

即然我们统计的是 L_x,R_x，此时要有贡献 0\sim x-1 只要都有就能放在 a_{L_x}\dots a_{R_x} 里面。

那做不到 0\sim x-1 都在 a_{L_x}\dots a_{R_x} 里面是怎么回事呢？唯一的可能就是 a 中就压根不存在某需要的数。

这里有单调性，没 0\sim a 中的任意一个都不能让 0\sim a+1 都出现，那么这个最多的连续出现数，不就是整个 a 的猫耳小减一嘛。

那么预处理总猫耳小即可，后面枚举 x 只需要枚举到这个“总猫耳小”。

零，在猫耳小问题中是一个特殊的存在。没有比零小的非负整数！

如果 a 中无零，那么这组数据的根基就没了，答案自然也成为棍母。直接输出 0 然后退出就行。具体见样例二。

特殊对待 x=0。那么 L,R不需要了，只需要 \mathcal O(n) 枚举每一个非零连续段，双指针统计每个右端点能贡献多少区间即可。

另一种思路，核心思想和上面的一样：

用 \operatorname{pos}_x 推 L,R 更方便，每次二分，用最近的、比 L 小和比 R 大的 \operatorname{pos}_{x,i} 更新 L 和 R，\operatorname{pos}_x=ø 则跳到输出答案环节，有 \operatorname{pos}_{x, i}\in[L, R] 就 continue，这样可以省去很多判断。

0x02 代码呈现

屎山版：

这里有些注释是赛时防止自己糊涂的。

#include "bits/stdc++.h"
using namespace std;
#define ch(opt, tar, ...) (tar = opt({tar, __VA_ARGS__}))
#define inlfc __attribute__((always_inline)) inline
#define isz(x) ((int)x.size())
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const int MAXN = 2e5 + 5, INF = 2e9;
int a[MAXN], lmin[MAXN] = {INF}, rmin[MAXN], l[MAXN], r[MAXN];
vector<int> pos[MAXN];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, wholemex;
    ll ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    for (int i = 1; i <= n; i ++)
        pos[a[i]].push_back(i);
    if (!pos[0].size()) {
        cout << 0; // 答案为棍母
        return 0;
    }
    for (wholemex = 0; wholemex <= n; wholemex ++)
        if (!pos[wholemex].size()) break; // 计算 a 的猫耳小
    for (int i = 1; i <= n; i ++)
        lmin[i] = min(lmin[i - 1], a[i]);
    for (int x = 1, i = n; x <= wholemex && i; x ++) {
        while (lmin[i - 1] < x) i --; // 单调不增算 L
        l[x] = i; // l_x = i_min | a_i < x
    }
    rmin[n + 1] = INF;
    for (int i = n; i; i --)
        rmin[i] = min(rmin[i + 1], a[i]);
    for (int x = 1, i = 1; x <= wholemex && i <= n; x ++) {
        while (rmin[i + 1] < x) i ++; // 单调不减算 R
        r[x] = i; // r_x = i_max | a_i < x
    }
    // x = 0
    for (int i = 1, j = 0; i <= n; i ++) {
        if (a[i]) j ++;
        else j = 0;
        ans += j; // 连续块长度为 j，以 i 为右端点可以贡献 j 个区间
    }
    // x > 0
    // 性质：a[L, R_x] ≠ x
    for (int x = 1; x <= wholemex; x ++) {
        if (!pos[x].size()) continue; // actually only when x=wholemex QwQ
        int L = l[x], R = r[x], _l, _r;
        auto it = lower_bound(pos[x].begin(), pos[x].end(), L); // 迭代器
        if (it != pos[x].end()) _r = *it;
        else _r = n + 1; // 后面没有 x 了
        if (it != pos[x].begin()) _l = *(it - 1);
        else _l = 0; // 前面没有 x 了
        if (_r <= R) continue; // [L,R]中有x
        ans += (ll)(L - _l) * (_r - R); // 别写反
    }
    cout << ans;
    return 0;
}

0x03 复杂度分析

线性套二分，\mathcal O(n \log n)。

0x~0 后记

数学老师：x 最大值要写 x_{max}。

时间不早了，求管理员先过下谢谢/bq。