糖果(Candy)

题目描述

2025 年青岛市中小学程序设计竞赛高中组 T2

小 A 喜欢糖果，它们有不同的种类，种类 $i$ 的美味等级为 $i$，等级数值越低表示糖果越美味，等级数值最小是 $0$。

小 A 喜欢收集更加美味的糖果。具体的，假设小 A 拥有若干个糖果，包含了集合 $S$ 内的种类，那么小 A 的下一个收集目标就是 $S$ 没出现过的美味等级数值最低的糖果（也就是小 A 没有获得的最美味的糖果）。

一天小 A 发现了 $n$ 颗糖果整齐地排成一行，第i 枚糖果的美味等级为 $a_i$。小 A 突发奇想：对于每个非空的区间$1 ≤ l ≤ r ≤ n$，假设他拥有了糖果 $a_l, a_{l+1}, . . . , a_r$，小 A的下一个收集目标是什么。小 A 不关心具体能收集到什么糖果，他只在意所有收集目标的美味等级之和。

帮助小 A 求出他的问题的答案。

【形式化题意】

定义 $\text{mex}(S)$ 表示集合 $S$ 内最小的没出现过的非负整数，如 $\text{mex}(\{0, 1, 3, 4\}) = 2$，$\text{mex}(\{1, 2, 5\}) = 0$，$\text{mex}(\{0, 1, 2, 3\}) = 4$。

定义 $S(l, r)$ 表示集合 $\{a_l, a_{l+1}, . . . , a_r\}$。

给定 $n$ 和一个长度为 $n$ 的非负整数序列 $a_1, a_2, . . . , a_n$，你需要求出

输入格式

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

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

输出格式

一行一个非负整数表示答案。

样例输入 #1

3
1 2 3

样例输出 #1

0

样例输入 #2

3
0 1 2

样例输出 #2

6

数据范围

样例 1 解释：

所有区间的 $\text{mex}$ 都是 $0$。

3
0 1 2

6

对于所有测试数据，保证 $1\le n \le 3\times 10^5,0 \le a_i \le 3\times 10^{5}$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1900。

测试点分布

出处：原题链接