P16383 [IATI 2025] Self-describing

Elena 又一次被分配了一个涉及具有特殊性质的子数组的问题。到目前为止，她觉得这些任务平淡无奇，于是把编写解决方案的工作留给了你们——IATI 参赛者。问题描述如下： 我们定义一个“自描述”数组 $b_0, b_1, \dots, b_{M-1}$ 是这样的数组：对于其中所有的 $b_i$，数字 $b_i$ 在整个数组中**恰好**出现 $b_i$ 次。例如，$[1, 2, 2]$、$[5,5,5,5,5]$、$[3,1,3,2,3,2]$ 都是“自描述”数组的例子，而 $[100, 1, 2, 2]$（$100$ 仅出现一次）、$[1,1,1,1,1]$（$1$ 出现了 $5$ 次）则不是“自描述”数组。 此外，对于一个数组 $b_0, b_1, \dots, b_{M-1}$，我们将“自描述”子数组定义为本身是“自描述”数组的子数组 $b_l, b_{l+1} \dots b_r$。 给定一个数组 $a_0, a_1, \dots, a_{N-1}$ 以及 $Q$ 个询问 $(l,r)$（满足 $l \leq r$）。对于每个询问，你需要针对所有满足 $l \leq l' \leq r' \leq r$ 的 $(l', r')$，统计其中“自描述”子数组的数量。 ### 实现细节 你需要实现以下两个过程： ```cpp void init(int N, int Q, const std::vector& a) ``` 该函数在每个测试点中只会被调用一次，为你的程序提供原始数组，该数组以向量形式传入，包含按顺序排列的 $N$ 个值 $a_0, a_1, \dots a_{N-1}$。 ```cpp long long query(int l, int r) ``` 该函数在每个测试点中会被调用 $Q$ 次，对应一个针对区间 $(l, r)$ 的询问，它应当返回该询问的答案。 ### 本地测试 为了在本地测试你的程序，我们提供了一个本地评测器和头文件。本地评测器按顺序读入 $N$、$Q$、$a_1, a_2, \dots, a_N$ 以及 $Q$ 个询问 $(l, r)$，调用你的 $\verb|init|$ 函数，然后输出你的程序对所有 $\verb|query|$ 调用所给出的答案。你可以自由修改本地评测器。

无

无

### 数据范围 - $1 \leq N, Q \leq 3 \times 10^5$ - 对所有 $0 \leq i \leq N - 1$，有 $1 \leq a_i \leq N$ - 对所有询问，有 $0 \leq l \leq r \leq N - 1$。 ### 子任务 | **子任务** | **分数** | **依赖子任务** | **$N$** | **$Q$** | **其他约束** | | :---: | :---: | :---: | :---: | :---: | :---: | | $0$ | $0$ | $-$ | $-$ | $-$ | 样例。 | | $1$ | $6$ | $-$ | $\leq 500$ | $=1$ | 唯一的询问为 $[1, N]$。 | | $2$ | $6$ | $1$ | $\leq 5000$ | $=1$ | 同上 | | $3$ | $39$ | $1-2$ | $\leq 3\times 10^5$ | $=1$ | 同上 | | $4$ | $11$ | $0-3$ | $\leq 3\times 10^5$ | $\leq 500$ | | | $5$ | $16$ | $0-4$ | $\leq 3 \times 10^5$ | $\leq 5\times10^4$ | $-$ | | $6$ | $22$ | $0-5$ | $\leq 3\times10^5$ | $\leq 5\times10^5$ | $-$ | 只有在成功通过某子任务的所有测试及其所需依赖子任务的所有测试后，才能获得该子任务的分数。 翻译由 DeepSeek V4 Pro 完成