[Algo Beat Contest 017 C] 交互题

GitHub跳转原题关系图 Canvas 关系图返回列表

按 mex 值贡献:分类，把条件转化为区间必须包含所有小于 x 的位置且避开所有 x 的位置。

OJ: luogu

题目 ID: P17234

难度:普及

标签:枚举计数mex区间

日期: 2026-08-11 07:37

前置题目

luogu P3662[USACO17FEB] Why Did the Cow Cross the Road II S固定长度滑动窗口的基础题，训练窗口右移时加新减旧维护状态，是本题 Subtask 2 区间增量维护的前置模型。

形式化题目

给定一个非负整数序列。对每个连续子区间，定义区间内部集合的 mex，以及删除该区间后剩余元素的最小值。要求统计这两个值相等的子区间个数；若补区间为空，其最小值视作无穷大。

暴力

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-11 07:37
 * update_at: 2026-08-11 18:01
 */
// brute.cpp：小数据暴力解，直接枚举所有区间并计算 mex 与补区间最小值。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 305;       // 暴力解复杂度为 O(n^3)，只适合小数据验证
const int INF = 1000000000; // 补区间为空时，cmin 保持这个很大的值

int n;
int a[MAXN];    // 输入数列，下标从 1 开始
int used[MAXN]; // used[x] = 1 表示当前区间内出现过值 x，用于求 mex

// 计算区间 [l, r] 的 mex：最小的没有在区间内出现过的非负整数。
int calc_mex(int l, int r) {
    // 清空标记数组，准备统计区间 [l, r] 内出现了哪些数
    for (int i = 0; i <= n + 1; i++) used[i] = 0;
    for (int i = l; i <= r; i++) {
        // 值太大时不可能成为 mex，不需要标记
        if (a[i] <= n + 1) used[a[i]] = 1;
    }

    // 从小到大找第一个没有出现过的数
    int mex_value = 0;
    while (used[mex_value]) mex_value++;
    return mex_value;
}

// 计算区间 [l, r] 的补区间最小值：由左边 [1, l-1] 和右边 [r+1, n] 两部分拼成。
int calc_cmin(int l, int r) {
    int cmin = INF;
    for (int i = 1; i < l; i++) cmin = min(cmin, a[i]);
    for (int i = r + 1; i <= n; i++) cmin = min(cmin, a[i]);
    return cmin;
}

void read_input() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
}

void solve() {
    long long ans = 0;
    // 枚举所有子区间的左右端点 [l, r]
    for (int l = 1; l <= n; l++) {
        for (int r = l; r <= n; r++) {
            // 满足 mex == cmin 的区间计入答案
            if (calc_mex(l, r) == calc_cmin(l, r)) ans++;
        }
    }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

暴力枚举所有区间，直接计算区间 mex 和补区间最小值，时间复杂度为 $O(n^3)$ ，只适合小数据验证和对拍。

思路

这道题有两个解法：解法一「按 mex 值分类 + 二分」适用于一般序列，是正式主解，对应 main.cpp；解法二利用「 $a$ 是 $0,1,\ldots,n-1$ 的一个排列」的特殊性质，把位置查找从二分简化为直接比较，对应 main-permutation.cpp。

两个解法共享同一个关键观察：固定可能的相等值 $x$ ，分析一个区间满足 mex = cmin = x 到底意味着什么。

若区间 mex 为 $x$ ，则区间内必须出现所有 $0,1,\ldots,x-1$ ，并且不能出现 $x$ 。

若补区间最小值为 $x$ ，则补区间中不能留下任何小于 $x$ 的数，并且要有至少一个 $x$ 。这说明所有小于 $x$ 的数的位置，都必须被选中的区间覆盖。

把两边合起来，对固定 $x$ ，合法区间等价于：

包含所有值小于 $x$ 的位置；
不包含任何值等于 $x$ 的位置；
全局至少存在一个值等于 $x$ 。

剩下的问题，就是如何高效处理“包含所有小于 $x$ 的位置，又避开值 $x$ 的位置”。

普通思索过程

如果不一开始就想到贡献法，可以先沿着数据范围逐步推进。

Subtask 1： $n\leqslant 100$ ，小数据暴力。

最直接的想法是枚举所有区间，再分别计算区间的 mex 和补区间的 cmin。也就是枚举 $[l,r]$ ，扫描区间内部求 mex，扫描补区间求 cmin。这个做法容易写，也适合验证题意，但复杂度太高，只能对应最小的数据范围。

复杂度为 $O(n^3)$ ，空间复杂度为 $O(n)$ 或 $O(V)$ ，其中 $V$ 是实际维护的值域大小。

Subtask 2： $n\leqslant 5000$ ，仍可枚举区间。

这时自然会想到仍然枚举区间，但把每个区间的 mex 和 cmin 维护得更快。例如固定左端点、右端点向右扩展时，可以用桶维护区间内每个值出现了几次，也用桶维护补区间里每个值还剩几次。这样能把判断一个区间是否合法的成本降下来，但思维仍然是“一个区间一个区间地检查”。

如果每次移动右端点都能均摊维护当前 mex 和补区间 cmin，目标复杂度可以做到 $O(n^2)$ ，空间复杂度为 $O(n)$ 。这里仍然没有用到贡献思想，只是把每个区间的判定变快。

这个基础动作可以先练 luogu/P3662。那题是固定长度窗口，每次窗口右移只需要“减去离开窗口的元素、加上进入窗口的元素”，正好对应窗口增量维护的最小模型。

Subtask 3： $a_i\leqslant 20$ ，桶的作用更明显。

如果值域很小，比如 $a_i\leqslant 20$ ，可能的相等值 $x$ 也很少。因为 cmin 必须是补区间里真实存在的最小值，而数组里没有大于 20 的值，所以只需要枚举 $x=0,1,\ldots,20$ 。

可以用桶 pos[v] 记录每个值 $v$ 出现过的所有位置。为了贴合 Subtask 3 的思考方式，这里不急着使用正式解法里的“随着 $x$ 增大逐步维护 $[L,R]$ ”和二分查找，而是每次固定 $x$ 后，暴力扫描 pos[0] 到 pos[x-1]，重新求所有小于 $x$ 的最小覆盖段 $[L,R]$ 。因为 $x$ 最多只有 20，这样不会超时。

先看 $x=0$ 。此时区间内不能有 0，并且补区间里必须留下至少一个 0。所以如果全局没有 0，答案直接为 0；如果全局有 0，所有不含 0 的区间都合法。把每个 0 当成分隔符，设某一段连续不含 0 的长度为 len，这一段内部任意子区间都不含 0，贡献为：

\frac{\text{len}(\text{len}+1)}{2}

再看 $x\ne 0$ 。mex = x 要求区间内有 $0,1,\ldots,x-1$ ，且不能有 $x$ ；cmin = x 要求补区间里不能留下任何小于 $x$ 的数，且要留下至少一个 $x$ 。合起来就是：所有小于 $x$ 的位置必须全部被区间覆盖，所有等于 $x$ 的位置必须避开。

设所有小于 $x$ 的位置形成的最小覆盖段为 $[L,R]$ 。合法区间必须满足 l <= L 且 r >= R。如果 $[L,R]$ 内部已经有值 $x$ ，那么这个 $x$ 无论如何都会被包含，贡献为 0。否则，设 prev 是 $[L,R]$ 左侧最近的 $x$ ，next 是 $[L,R]$ 右侧最近的 $x$ ，合法左端点有 $L-\text{prev}$ 种，合法右端点有 $\text{next}-R$ 种，所以固定 $x$ 的贡献为：

(L-\text{prev})\times(\text{next}-R)

核心片段如下：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75const int K = 20;
vector<int> pos[25];

long long count_no_zero(int n) {
    long long res = 0;
    int last = 0;

    for (int i = 0; i < (int)pos[0].size(); i++) {
        int p = pos[0][i];
        int len = p - last - 1;
        res += 1LL * len * (len + 1) / 2;
        last = p;
    }

    int len = n - last;
    res += 1LL * len * (len + 1) / 2;
    return res;
}

bool get_cover_range(int x, int n, int &L, int &R) {
    L = n + 1;
    R = 0;

    // Subtask 3 的小值域暴力：重新扫描 0..x-1 的所有位置。
    for (int v = 0; v < x; v++) {
        if (pos[v].empty()) return false;

        for (int i = 0; i < (int)pos[v].size(); i++) {
            int p = pos[v][i];
            if (p < L) L = p;
            if (p > R) R = p;
        }
    }

    return true;
}

bool get_nearest_x(int x, int L, int R, int n, int &prev_x, int &next_x) {
    prev_x = 0;
    next_x = n + 1;

    // 扫描所有 x：如果 x 落在 [L,R] 内，就无法避开。
    for (int i = 0; i < (int)pos[x].size(); i++) {
        int p = pos[x][i];

        if (L <= p && p <= R) return false;
        if (p < L && p > prev_x) prev_x = p;
        if (p > R && p < next_x) next_x = p;
    }

    return true;
}

long long solve_subtask3(int n) {
    long long ans = 0;

    // x = 0：只统计不含 0 的区间。
    if (pos[0].empty()) return 0;
    ans += count_no_zero(n);

    for (int x = 1; x <= K; x++) {
        // 补区间里必须有 x；如果全局没有 x，后面更大的 x 也不可能。
        if (pos[x].empty()) break;

        int L, R;
        if (!get_cover_range(x, n, L, R)) break;

        int prev_x, next_x;
        if (!get_nearest_x(x, L, R, n, prev_x, next_x)) continue;

        ans += 1LL * (L - prev_x) * (next_x - R);
    }

    return ans;
}

单独看一次 get_cover_range，最坏复杂度确实是 $O(n)$ 。但在 Subtask 3 中， $x$ 最多只枚举 1..20，所以这个函数最多调用 20 次。get_nearest_x 每次只扫描 pos[x]，所有 x 的位置桶总长度为 $n$ 。因此总时间复杂度是 $O(20n)$ ，也就是 $O(n)$ 级别；空间复杂度为 $O(n+21)$ 。这一步能看到一个信号：本题真正重要的不是大数本身，而是小值和它们的位置。

Subtask 4： $a$ 是排列，位置视角变清楚。

排列中每个值只出现一次，所以固定 $x$ 后， $0,1,\ldots,x-1$ 的位置是一批必须关注的点。它们的最左位置和最右位置形成一个最小覆盖段 $[L,R]$ 。如果要让 mex = cmin = x，区间必须包住这些小于 $x$ 的位置，同时不能碰到值 $x$ 的位置。

这就是从枚举区间转向枚举贡献的关键：固定 $x$ 以后，合法区间不是任意形状，而是“必须覆盖 $[L,R]$ ，并避开值 $x$ 的障碍”。在排列里，值 $x$ 只有一个位置，所以只要判断它在 $[L,R]$ 左边、右边还是内部，就能直接算贡献。

按 $x$ 从小到大枚举，每次把 pos[x-1] 加入 $[L,R]$ ，并直接查看唯一的 pos[x]，复杂度为 $O(n)$ ，空间复杂度为 $O(n)$ 。

Subtask 5：无特殊限制，把一个障碍推广成多个障碍。

完整数据只是把“一个值 $x$ 的位置”推广成“多个值 $x$ 的位置”。小于 $x$ 的所有位置仍然可以压缩成 $[L,R]$ ；值为 $x$ 的位置仍然是不能碰到的障碍。于是只需要找 $[L,R]$ 左侧最近的 $x$ 和右侧最近的 $x$ ，左右端点的可选数量相乘，就是固定 $x$ 的贡献。

用位置表保存每个值出现的位置，枚举 $x$ 时维护所有小于 $x$ 的位置范围 $[L,R]$ ，再在 pos[x] 中二分找到左右最近的 $x$ 。时间复杂度为 $O(n\log n)$ ，空间复杂度为 $O(n)$ 。

所以真正的转折不在代码，而在计数对象的改变：不要问“这个区间是否合法”，而要问“如果答案值固定为 $x$ ，哪些位置被强制包含，哪些位置必须避开”。

真人思考🤔

说实话，这道题的核心可以压缩成一句话：按相等的 mex 值 $x$ 分类贡献，在全局存在 $x$ 的前提下，把条件转化为“区间必须包含所有小于 $x$ 的位置，并避开所有等于 $x$ 的位置”。

如果没有做过类似的贡献计数题，从枚举区间直接跳到这句话确实很难。一条更真实的发现路径，是先写出暴力，再用极端情形逐步观察 $x=0,1,2$ 时到底发生了什么。

先写暴力，能为后面的思考提供什么？

暴力会逐个区间计算 mex 和 cmin。虽然它不能通过完整数据，但观察合法区间时会发现：两个量既然相等，就可以把这个公共值记作 $x$ ，尝试分别研究“哪些区间贡献给 $x=0$ 、哪些贡献给 $x=1$ ”。这一步把“枚举区间”转成了“按答案值分类”的可能方向。

为什么先研究极端情形 $x=0$ ？

mex = 0 只要求区间内没有 0；cmin = 0 要求补区间里至少留下一个 0。只要全局存在 0，一个不含 0 的区间就会把所有 0 留在补区间中，因此一定合法。于是把每个 0 当成分隔符，统计每段连续非零区间中的子区间数量即可。

这里要注意：全局只有一个 0，并不意味着 $x=0$ 的贡献一定为 $0$ 。只要选择的区间避开这个 0，唯一的 0 就会留在补区间里；只有序列中不存在可选的非空无零区间时，这部分贡献才为 $0$ 。

接下来研究 $x=1$ ，究竟卡在哪里？

先把两个条件分别翻译：

mex = 1：区间内至少有一个 0，并且没有 1；
cmin = 1：补区间内没有 0，并且至少有一个 1。

把它们合起来后，才会出现真正关键的强制条件：补区间里不能有 0，所以不只是“区间里有一个 0”，而是所有 0 都必须在区间里；同时区间里不能有 1，所以所有 1 都必须留在补区间里。

因此， $x=1$ 的合法区间等价于：包含所有 0 的位置，并避开所有 1 的位置。设所有 0 的最小覆盖段为 $[L,R]$ ：如果全局没有 1，或者 $[L,R]$ 内已经夹着一个 1，那么 $x=1$ 的贡献为 $0$ ；否则设 $[L,R]$ 左右最近的 1 分别位于 prev 和 next，贡献就是

(L-\text{prev})\times(\text{next}-R)。

从 $x=1$ 怎样推广到任意 $x$ ？

再试一次 $x=2$ ：mex = 2 要求区间内有 0,1 且没有 2；cmin = 2 要求补区间里没有 0,1 且至少有一个 2。合并后就是“包含所有 0,1 的位置，避开所有 2 的位置”。此时模式已经出现，一般的 $x$ 只是把 0,1 换成 $0,1,\ldots,x-1$ 。

所以这条真人思考路径可以概括为：先用暴力获得观察对象，再研究退化情形 $x=0$ ，接着攻克最小的非平凡情形 $x=1$ ，最后用 $x=2$ 验证并推广。极限法负责打开缺口，而真正完成跨越的观察是：cmin = x 会把“区间里出现小于 $x$ 的数”强化成“所有小于 $x$ 的出现位置都必须被区间覆盖”。

解法一：通用解法（按 mex 值分类 + 二分）

思路

“核心思路”

设区间 $C(x)$ ,表示包含所有 $0,1,2 \cdots x$ 的最小的区间,ps 这个区间可以包含>=x的数字,但是必须把所有的 $0,1,2 \cdots ,x$ 全部包含.
则显然发现 $C(x) \subset C(x+1)$ ,这说明具有单调性
根据做题的经验(双指针,单调队列等): 单调性 就是优化的关键
基本上能降低一个数量级的优化: 要么单调性(可预测),要么数据结构

解法一不是另起炉灶，而是继续优化 Subtask 3 中最耗时的重复操作：对每个 $x$ 重新计算最小覆盖段。

先单独处理 $x=0$ 。此时没有“小于 $0$ 的值”需要包含，合法区间只需要不包含 0。因为全局存在 0 时，不含 0 的区间一定会把某个 0 留在补区间里，所以贡献就是所有不含 0 的连续段的子区间数量之和。

这里容易混淆的是补区间条件。mex = 0 等价于“选中的区间里没有 0”；cmin = 0 等价于“删掉这个区间以后，剩下的元素里还有至少一个 0”。如果整个序列本来存在 0，并且当前区间不含 0，那么所有 0 都会留在补区间里。又因为序列元素都是非负整数，补区间里只要有 0，最小值就一定是 0。

所以 $x=0$ 时不用再额外检查补区间，只要把每个 0 当成分隔符。对于一段长度为 len 的不含 0 的连续段，它里面任意子区间都不含 0，贡献为 $\frac{\text{len}(\text{len}+1)}{2}$ 。

接下来把 Subtask 3 的思路推广到通用数据。Subtask 3 里可以对每个 $x$ 重新扫描 pos[0]..pos[x-1] 来求最小覆盖段 $[L,R]$ ，因为 $x$ 最多只有 20。但通用数据下 $x$ 可能达到 $n$ ，如果每次都重新扫描所有小于 $x$ 的位置，就会退化成 $O(n^2)$ 。

相邻两个 $x$ 所需要覆盖的位置，有什么关系？

设 $C(x)$ 表示“所有值小于 $x$ 的出现位置”的最小覆盖段。也就是说， $C(x)$ 必须覆盖值为 $0,1,\ldots,x-1$ 的全部出现位置，而不是每个值任意选择一个位置。这是因为 cmin = x 要求补区间里不能留下任何小于 $x$ 的数。覆盖段内部可以顺带夹着大于等于 $x$ 的值，它们并不参与 $C(x)$ 的定义。

当 $x$ 增加到 $x+1$ 时，必须覆盖的位置只增加了 pos[x] 中的所有位置，原来已经加入的位置一个也不会删除。因此 $C(x+1)$ 一定包含 $C(x)$ ：左端点只可能向左移动，右端点只可能向右移动。

这就是本题可以利用的单调性。它不是普通双指针中“两个端点都向右移动”的单调性，而是维护对象随着 $x$ 增大只增不删。单调性本身不保证复杂度一定下降，但它提示我们可以增量维护状态：处理当前 $x$ 时，只把 pos[x-1] 中的位置加入覆盖段，不必重新执行 get_cover_range(x)：

cpp

1
2
3
4
5for (int i = 0; i < (int)pos[x - 1].size(); i++) {
    int p = pos[x - 1][i];
    if (p < L) L = p;
    if (p > R) R = p;
}

这样每个位置只会被加入一次，Subtask 3 中 get_cover_range 的重复扫描就被优化掉了。这个观察的价值不只是“发现了单调性”，而是明确找到了可以复用的上一轮状态。

完成覆盖段的增量维护后，还要找值 $x$ 的障碍位置。Subtask 3 直接扫描 pos[x]；当前正式代码使用 lower_bound，在有序位置表中找到 $[L,R]$ 左右最近的 $x$ 。

对于 $x\geqslant 1$ ，维护所有值小于 $x$ 的位置的最小值 $L$ 和最大值 $R$ 。任何合法区间必须包含整个 $[L,R]$ 。如果 $[L,R]$ 中已经有值 $x$ ，则无论如何都会包含 $x$ ，贡献为 $0$ 。

这里的思考顺序是：先不要枚举区间，而是固定 $x$ 后看哪些位置被强制包含。mex = x 要求区间内出现 $0,1,\ldots,x-1$ ；cmin = x 又要求补区间里不能留下任何小于 $x$ 的数，所以所有小于 $x$ 的位置都必须被当前区间覆盖。把这些位置压缩成最小覆盖段 $[L,R]$ 后，合法区间只能是在 $[L,R]$ 的基础上向左、向右扩展。

与此同时，mex = x 还要求区间内不能出现 $x$ ，所以值为 $x$ 的位置就像不能碰到的障碍。如果障碍已经落在必须覆盖的 $[L,R]$ 内，那么不管左右端点怎么选，区间都会包含这个 $x$ ，贡献只能是 $0$ 。

否则，找到 $[L,R]$ 左侧最近的 $x$ 的位置 prev，以及右侧最近的 $x$ 的位置 next。合法左端点可以选在 prev+1 到 $L$ ，合法右端点可以选在 $R$ 到 next-1，所以贡献为：

(L-\text{prev})\times(\text{next}-R)。

这个乘法的含义是：左端点只负责不越过左边最近的 $x$ ，右端点只负责不越过右边最近的 $x$ 。只要左端点落在 prev+1 到 $L$ ，右端点落在 $R$ 到 next-1，区间就一定包住所有小于 $x$ 的位置，并且不会碰到任何值为 $x$ 的位置。反过来，任何合法区间也必须这样选端点，所以左右端点数量可以直接相乘。

按 $x=1,2,3,\ldots$ 枚举，并逐步把值 $x-1$ 的所有位置加入 $[L,R]$ 。如果某个 $x$ 不存在，就可以停止，因为更大的 mex 要求 $0\ldots x$ 都出现，已经不可能。

下面用样例三 [0,1,0,2] 展示几个关键值的统计：

$x$	小于 $x$ 的位置范围 $[L,R]$	值 $x$ 的位置	贡献说明	贡献
0	无	1, 3	不含 0 的区间为 `[2,2]`、`[4,4]`	2
1	`[1,3]`	2	范围内含 1，无法避开	0
2	`[1,3]`	4	左端点只能选 1，右端点只能选 3	1

表中可以看到，固定 $x$ 后并不是枚举所有区间，而是只看“小于 $x$ 的所有位置形成的最小覆盖段”。区间必须包住这个覆盖段，又不能碰到值 $x$ ，于是左右端点数量可以直接相乘。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-11 07:37
 * update_at: 2026-08-11 22:22
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXV = 200005;

int n;
int a[MAXV];
vector<int> pos[MAXV]; // pos[v] 保存值 v 在数组中的所有位置（下标从 1 开始）

void read_input() {
    cin >> n;
    for (int i = 0; i <= n + 1; i++) pos[i].clear();
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] <= n) pos[a[i]].push_back(i); // 值 > n 不可能成为 mex=cmin 的答案，忽略
    }
}

// 统计 mex(l,r) = cmin(l,r) = 0 的区间数量。
// 条件等价于：区间内不含任何 0（mex=0），
// 且补区间里至少有一个 0（cmin=0），即区间没覆盖全部 0。
long long count_no_zero() {
    long long ans = 0;
    int last = 0; // 上一个 0 的位置，初始相当于位置 0 处有一个虚拟 0
    for (int i = 0; i < (int)pos[0].size(); i++) {
        int len = pos[0][i] - last - 1; // 两个相邻 0 之间不含 0 的连续段长度
        ans += 1LL * len * (len + 1) / 2; // 该段内任取一个子区间都不含 0
        last = pos[0][i];
    }
    int len = n - last; // 最后一个 0 之后的连续段
    ans += 1LL * len * (len + 1) / 2;
    return ans;
}

// 把值 v 的所有位置并入最小覆盖段 [L,R]。
// 随着 x 增大，覆盖段只增不删，因此每个位置只会被加入一次。
void merge_into_cover(int v, int &L, int &R) {
    for (int i = 0; i < (int)pos[v].size(); i++) {
        int p = pos[v][i];
        if (p < L) L = p;
        if (p > R) R = p;
    }
}

// 找 [L,R] 左侧最近的 x 与右侧最近的 x（不含则用哨兵位置 0 / n+1）。
// 若覆盖段 [L,R] 内已经存在 x，则任何合法区间都无法避开它，返回 false。
bool get_nearest_x(int x, int L, int R, int &prev_x, int &next_x) {
    vector<int>::iterator it = lower_bound(pos[x].begin(), pos[x].end(), L);
    prev_x = 0;      // 左侧哨兵，表示位置 0 处虚拟一个 x
    next_x = n + 1;  // 右侧哨兵，表示位置 n+1 处虚拟一个 x
    if (it != pos[x].end()) {
        next_x = *it;
        if (*it <= R) return false;
    }
    if (it != pos[x].begin()) {
        --it;
        prev_x = *it;
    }
    return true;
}

// 对每个 x >= 1：mex(l,r) = cmin(l,r) = x 等价于
// 1) 区间 [l,r] 覆盖所有值 < x 的位置（保证 mex >= x 且补区间不含 < x 的值）；
// 2) 区间 [l,r] 不覆盖任何值 = x 的位置（保证 mex <= x 且补区间含 x，cmin = x）。
long long solve() {
    long long ans = 0;

    if (pos[0].empty()) {
        // 数组里没有 0：任意区间的 mex 恒为 0，
        // 而补区间最小值至少为 1（或 +inf），不可能相等。
        return 0;
    }
    ans += count_no_zero();

    int L = n + 1; // [L,R] 是所有值 < x 的位置的最小覆盖段
    int R = 0;
    for (int x = 1; x <= n; x++) {
        merge_into_cover(x - 1, L, R); // 覆盖段增加值 x-1 的所有位置

        if (pos[x].empty()) break; // 缺少值 x，mex 不可能再等于更大的值

        int prev_x, next_x;
        if (!get_nearest_x(x, L, R, prev_x, next_x)) continue;

        // 左端点 l 可在 (prev_x, L] 中任选，右端点 r 可在 [R, next_x) 中任选，
        // 左右端点选择互不影响，贡献为可选数量的乘积。
        ans += 1LL * (L - prev_x) * (next_x - R);
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    cout << solve() << '\n';

    return 0;
}

复杂度

每个位置只会加入一次对应值的位置表。枚举每个 $x$ 时，对 pos[x] 做一次二分查找，因此时间复杂度为 $O(n\log n)$ 。

位置表和输入数组占 $O(n)$ 空间。

解法二：排列特殊性质写法

思路

如果数列是 $0,1,\ldots,n-1$ 的一个排列，还可以把解法一进一步简化。因为每个值只出现一次，值 $x$ 的位置只有一个 pos[x]，不需要在位置表里二分找左右最近的 $x$ 。

先处理 $x=0$ ：排列中只有一个 0，所有不含 0 的区间都满足 mex = cmin = 0，贡献为 0 左右两侧不含 0 的连续段的子区间数之和。

设当前所有小于 $x$ 的值的位置范围仍为 $[L,R]$ 。若 pos[x] 在 $[L,R]$ 内，贡献为 $0$ 。若 pos[x] < L，合法区间必须从 pos[x] 右侧开始并包含 $[L,R]$ ，贡献为 $(L-pos[x])\times(n-R+1)$ 。若 pos[x] > R，贡献为 $L\times(pos[x]-R)$ 。

这个写法只适用于排列特殊性质，不能替代通用解法，但复杂度从 $O(n\log n)$ 降到 $O(n)$ 。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-11 10:52
 * update_at: 2026-08-11 10:52
 */
// main-permutation.cpp：排列特殊性质解法，只适用于 a 是 0..n-1 的一个排列。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

int n;
int a[MAXN];
int pos[MAXN]; // pos[x] 表示值 x 在排列中的位置

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pos[a[i]] = i;
    }

    long long ans = 0;

    // x = 0：排列中只有一个 0，所有不含 0 的区间都合法。
    int p0 = pos[0];
    ans += 1LL * (p0 - 1) * p0 / 2;
    ans += 1LL * (n - p0) * (n - p0 + 1) / 2;

    int left_bound = pos[0];
    int right_bound = pos[0];

    for (int x = 1; x <= n - 1; x++) {
        int px = pos[x];
        if (left_bound <= px && px <= right_bound) {
            // 值 x 已经落在必须包含的 [L,R] 内，mex 不可能等于 x。
        }
        else if (px < left_bound) {
            ans += 1LL * (left_bound - px) * (n - right_bound + 1);
        }
        else {
            ans += 1LL * left_bound * (px - right_bound);
        }

        if (px < left_bound) left_bound = px;
        if (px > right_bound) right_bound = px;
    }

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

复杂度

每个 $x$ 只处理一次位置，时间复杂度为 $O(n)$ 。

输入数组和位置数组占 $O(n)$ 空间。

复杂度对比

下面这张表对比两个解法的复杂度与适用条件：

解法	时间复杂度	空间复杂度	适用条件
解法一：通用解法	$O(n\log n)$	$O(n)$	任意非负整数序列
解法二：排列特殊性质	$O(n)$	$O(n)$	$a$ 是 $0,1,\ldots,n-1$ 的一个排列

解法二更快，但只在排列数据下成立；正式主解仍以解法一为准。

题目推荐

“区间贡献计数”并不是某个固定算法，而是一种枚举对象的转换：

不再枚举每个区间是否合法，而是固定某个贡献者，计算它能产生多少个合法区间。

P17234 固定的贡献者不是某个位置，而是公共值 $x$ 。

最适合的前置题

USACO 1492 Making Mexes

这道题训练固定目标 mex： $0,1,\ldots,x-1$ 必须出现，而 $x$ 必须消失。它不涉及区间，但能先建立“按 mex 值分类”的意识。
USACO 1155 Lonely Photo

固定唯一的少数派位置，找到左右障碍，再计算左右选择数。它的核心贡献形式是

$\text{left}\times\text{right}。$
这是最适合训练“从枚举区间转向枚举贡献者”的题。
LeetCode 907 子数组的最小值之和

固定位置 $i$ 作为区间最小值，寻找左右第一个阻止它继续扩展的位置，贡献为

$(i-L)(R-i)。$
它和 P17234 都具有“固定贡献者、寻找左右障碍、左右选择数相乘”的结构。rbook 的单调栈文章也专门介绍了这个模型。
Codeforces 1699C The Third Problem

这是一道很好的过渡题。它按数值从小到大处理排列，持续维护包含 $0,1,\ldots,x-1$ 位置的最小覆盖段，训练的正是

$C(x)\subseteq C(x+1)。$
不过它统计的是排列方案，而不是合法区间。

与 P17234 最相似的题

最接近的是 Codeforces 1793D Moscow Gorillas。它对两个排列统计 mex 相同的区间。固定 mex 为 $x$ 后，两道题的对应关系如下：

P17234	CF1793D
覆盖一个数组中所有小于 $x$ 的位置	覆盖两个排列中所有小于 $x$ 的位置
避开所有等于 $x$ 的位置	避开 $x$ 在两个排列中的位置
统计左右端点选择	统计左右端点选择

因此它几乎就是 P17234 核心模型的“双排列版本”。这道题更适合作为学完 P17234 后的同模型练习，而不是前置题。

第二相似的是 Codeforces 1744F MEX vs MED。它同样会按 mex 值分类贡献，维护覆盖 $0,1,\ldots,x-1$ 的最小区间 $[L,R]$ ，再统计可以从 $[L,R]$ 扩展出的区间。区别是它还要把 mex > median 转换成区间长度限制，因此比 P17234 多了一层约束。

更广泛的贡献计数练习

USACO 1470 Cow Checkups：固定位置匹配关系，计算每对位置由多少个反转区间产生。
Luogu P1950 长方形：把矩形计数转成每行直方图中所有子数组最小值的贡献，难度更高。
Luogu P5788 单调栈：只训练寻找最近障碍，不直接做贡献计数。

总结

这题的关键是按相等值 $x$ 分类。mex = x 约束区间内部必须有小于 $x$ 的值且不能有 $x$ ；cmin = x 又强制所有小于 $x$ 的值不能留在补区间。合并后就得到“包住所有小于 $x$ 的位置，避开所有 $x$ 的位置”。

这个等价条件把区间计数变成了左右端点的乘法计数，是整题最重要的转折。

图示解析

这张图串起按值分类后的计数路线，并标出两个解法的分叉：

text

1
2
3
4
5
6
7固定相等值 x
|- mex = x：区间内有 0..x-1，且没有 x
`- cmin = x：补区间没有 <x，且有 x
   `- 所有 <x 的位置必须在区间内
      `- 区间包住 [L,R]，并避开最近的 x
         |- 通用解法：二分找最近的 x，左端点数 × 右端点数
         `- 排列写法：pos[x] 唯一，直接比较 [L,R] 并计数

先把两个条件都翻译成对元素位置的限制，再合并共同部分。合并后，所有小于 $x$ 的位置只需要用一个最小覆盖段 $[L,R]$ 表示。值 $x$ 的最近位置则限制左右端点能扩展到哪里，因此答案可以用乘法原理计算。

排列写法只是把“找最近的 $x$ ”这一环，用“值 $x$ 的位置唯一”直接代替，其余计数逻辑和通用解法一致。

P17234 [Algo Beat Contest 017 C] 交互题

题目背景

[省选联考 2026] 排列游戏

题目描述

给定一个长度为 $n$ 的数列 $a_1, a_2, \dots, a_n$ 。

对于一个子区间 $[l, r]$ （ $1 \leq l \leq r \leq n$ ），定义其补区间为原数列去掉该子区间后剩余的部分，即由两部分 $[1, l-1]$ 和 $[r+1, n]$ 构成（若某部分为空则忽略）。

定义：

$\operatorname{mex}(l, r)$ 为子区间 $[l, r]$ 中所有数构成的集合的 $\operatorname{mex}$ 值，即最小的未出现在该区间中的非负整数。
$\operatorname{cmin}(l, r)$ 为补区间中所有数的最小值。特别地，若补区间为空（即 $l=1$ 且 $r=n$ ），则 $\operatorname{cmin}$ 视为 $+\infty$ 。

求有多少个子区间 $[l, r]$ ，满足 $\operatorname{mex}(l, r) = \operatorname{cmin}(l, r)$ 。

输入格式

第一行输入一个正整数 $n$ 。

第二行输入 $n$ 个非负整数 $a_1, a_2, \dots, a_n$ 。

输出格式

输出一行一个整数，表示满足条件的子区间个数。

输入输出样例 #1

输入 #1

text

1
25
1 0 2 1 3

输出 #1

text

输入输出样例 #2

输入 #2

text

1
23
1 2 3

输出 #2

text

输入输出样例 #3

输入 #3

text

1
24
0 1 0 2

输出 #3

text

说明/提示

【样例 #1 解释】

数列为 $[1, 0, 2, 1, 3]$ ，共有 $15$ 个子区间。满足条件的 $10$ 个子区间如下：

$[l, r]$	区间内元素	$\operatorname{mex}$	补区间元素	$\operatorname{cmin}$	是否相等
$[1,1]$	$\{1\}$	$0$	$[0,2,1,3]$	$0$	$\checkmark$
$[1,2]$	$\{1,0\}$	$2$	$[2,1,3]$	$1$
$[1,3]$	$\{1,0,2\}$	$3$	$[1,3]$	$1$
$[1,4]$	$\{1,0,2,1\}$	$3$	$[3]$	$3$	$\checkmark$
$[1,5]$	$\{1,0,2,1,3\}$	$4$	$[]$	$+\infty$
$[2,2]$	$\{0\}$	$1$	$[1,2,1,3]$	$1$	$\checkmark$
$[2,3]$	$\{0,2\}$	$1$	$[1,1,3]$	$1$	$\checkmark$
$[2,4]$	$\{0,2,1\}$	$3$	$[1,3]$	$1$
$[2,5]$	$\{0,2,1,3\}$	$4$	$[1]$	$1$
$[3,3]$	$\{2\}$	$0$	$[1,0,1,3]$	$0$	$\checkmark$
$[3,4]$	$\{2,1\}$	$0$	$[1,0,3]$	$0$	$\checkmark$
$[3,5]$	$\{2,1,3\}$	$0$	$[1,0]$	$0$	$\checkmark$
$[4,4]$	$\{1\}$	$0$	$[1,0,2,3]$	$0$	$\checkmark$
$[4,5]$	$\{1,3\}$	$0$	$[1,0,2]$	$0$	$\checkmark$
$[5,5]$	$\{3\}$	$0$	$[1,0,2,1]$	$0$	$\checkmark$

共有 $10$ 个区间满足条件。

【样例 #2 解释】

数列为 $[1, 2, 3]$ 。整个数列中没有 $0$ ，因此任意子区间 $[l, r]$ 的 $\operatorname{mex}$ 恒为 $0$ 。而补区间的最小值至少为 $1$ （除非补区间为空，此时 $\operatorname{cmin} = +\infty$ ），因此不存在满足 $\operatorname{mex} = \operatorname{cmin}$ 的区间，答案为 $0$ 。

【样例 #3 解释】

数列为 $[0, 1, 0, 2]$ ，共有 $10$ 个子区间。满足条件的 $3$ 个子区间如下：

$[l, r]$	区间内元素	$\operatorname{mex}$	补区间元素	$\operatorname{cmin}$	是否相等
$[1,3]$	$\{0,1\}$	$2$	$[2]$	$2$	$\checkmark$
$[2,2]$	$\{1\}$	$0$	$[0,0,2]$	$0$	$\checkmark$
$[4,4]$	$\{2\}$	$0$	$[0,1,0]$	$0$	$\checkmark$

其中 $[1,3]$ 的 $\operatorname{mex}=2$ 且补区间最小值为 $2$ （补区间恰好有一个 $2$ ）； $[2,2]$ 和 $[4,4]$ 则对应 $\operatorname{mex}=\operatorname{cmin}=0$ 的情况。

【数据范围与约定】

对于所有测试数据，保证：

$1\le n\le 2\times 10^5$
$0\le a_i\le 2\times 10^5$

本题开启子任务捆绑。

Subtask	特殊限制	分值
1	$n\le 100$	15
2	$n\le 5000$	15
3	对所有 $i$ ，均有 $0\le a_i\le 20$	15
4	$a$ 是 $0,1,\dots,n-1$ 的一个排列	15
5	无特殊限制	40

[Algo Beat Contest 017 C] 交互题

目录

形式化题目

暴力

思路

普通思索过程

真人思考🤔

解法一：通用解法（按 mex 值分类 + 二分）

思路

代码

复杂度

解法二：排列特殊性质写法

思路

代码

复杂度

复杂度对比

题目推荐

最适合的前置题

与 P17234 最相似的题

更广泛的贡献计数练习

推荐学习顺序

总结

图示解析