BCSP-X · 2024 BCSP-X 上半年活动基础知识测评（小学高年级组） 第 19 题

三、完善程序（单选题，每小题 3 分，共计 30 分）

（1）给定长度 $n$ 的整数序列 $a_1, a_2, \dots, a_n$，以及 $q$ 个询问。每个询问将指定两个整数 $l, r$，请判断下标在 $l$ 与 $r$ 之间的序列元素（包括 $a_l$ 与 $a_r$）是否互不相同。输入数据保证 $1 \leq n, q \leq 100000$，$1 \leq a_i \leq n$，$1 \leq l \leq r \leq n$。

试用最优选项补全程序。

#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 5;
int n, q, a[MAXN], last[MAXN], tmp[MAXN], mxlast[MAXN];
int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        ___①___;
        ___②___;
        ___③___;
        if (last[i] > mxlast[i])
            mxlast[i] = last[i];
    }
    while (___④___) {
        int l, r;
        cin >> l >> r;
        if (___⑤___)
            cout << "No" << endl;  // 区间内存在相同元素
        else
            cout << "YES" << endl;  // 互不相同
    }
    return 0;
}

1. ① 处应填（ ）。 A. last[tmp[i]] = a[i] B. last[i] = tmp[a[i]] C. `

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题考的是区间内元素是否重复的经典判重技巧——离散化 + 前缀最值。拿到题先别急着填空，盯着数组下标和值的关系：题目给的是值域在 1~n 的序列，但我们要查的是“某个值上次出现的位置”，所以必须建一个映射表把值转成位置，同时维护一个单调递增的前缀数组，这样区间判重就变成一次比较 mxlast[r]>=l。

最容易栽跟头的地方是把 tmp 和 last 的用途搞反。tmp 是用来存“值对应的最新位置”，last 是用来存“位置对应的值”，填反了后面逻辑全崩。其次，前缀数组 mxlast 的初始化很多人会写成 0 或 MAXN，其实应该用 mxlast[i-1] 累加，因为我们要的是从 1 到 i 的最大值，初始值必须继承前一个。还有循环控制，q 个询问，用 q-- 最稳妥，写成 !(q--) 或 !(--q) 容易在边界条件上出错。最后判断条件，区间内有重复等价于“最晚出现的位置>=左端点”，写成 <= 就反了。

这道题考查的是区间内元素是否重复的判重技巧，核心是离散化思想与前缀最值维护。命题人喜欢挖的坑就在数组下标与值的对应关系上，以及前缀数组的初始化逻辑。拿到题先想：题目给的是值域在 1~n 的序列，但我们要查的是“某个值上次出现的位置”，所以必须建一个映射表把值转成位置，同时维护一个单调递增的前缀数组，这样区间判重就变成一次比较 mxlast[r]>=l。

具体怎么填？看①处，循环里刚读入 a[i]，我们需要记录“值 a[i] 第一次出现的位置是 i”，所以 tmp 数组应该存值到位置的映射，即 tmp[a[i]]=i，选 D。②处要记录“位置 i 对应的值是什么”，所以 last[i]=tmp[i]，选 B。③处维护前缀最值，mxlast[i] 应该是 1~i 中 tmp 的最大值，自然用 mxlast[i-1] 累加，选 D。④处控制询问次数，q 个询问，用 q-- 最稳妥，选 A。⑤处判断区间 [l,r] 是否有重复，等价于“最晚出现的位置>=左端点”，即 mxlast[r]>=l，选 D。

推导过程再细说一遍：tmp 数组把值映射成位置，last 数组把位置映射成值，这样我们就能在 O(1) 时间内知道某个位置的值，以及某个值上次出现的位置。mxlast 数组记录了从 1 到 i 的最大 tmp 值，也就是前缀里最新出现的位置。对于询问 [l,r]，如果 mxlast[r]>=l，说明在 l 到 r 之间有一个值，它的前缀最晚位置超过了 l，意味着这个值在 l 左边也出现过，区间内必有重复，输出 No；否则输出 Yes。

避坑指南：tmp 和 last 千万别填反，否则后面逻辑全崩。mxlast 的初始化一定要用 mxlast[i-1]，写成 0 或 MAXN 都会导致前缀最值计算错误。循环控制用 q-- 最稳妥，写成 !(q--) 或 !(--q) 容易在边界条件上出错。最后判断条件，区间内有重复等价于“最晚出现的位置>=左端点”，写成 <= 就反了。考频方面，这类前缀最值判重题在 CSP-J/S 和 GESP 中属于高频考点，每年都有类似变体，比如区间和、区间最大子段和等，但核心思想不变。预测未来可能继续考区间判重，或者结合线段树、树状数组做动态版本，难度会逐步提升。