G - mex 之和 / ΣШX

题目描述

给定一个长度为 $N$ 的非负整数序列 $A = (A_1, \dots, A_N)$。

求所有满足 $1 \leq l \leq r \leq N$ 的整数对 $(l, r)$ 对应的 $\mathrm{mex}({A_l, \cdots, A_r})$ 之和。

其中，$\mathrm{mex}({A_l, \cdots, A_r})$ 表示未在 $A_l, \cdots, A_r$ 中出现的最小非负整数。

数据范围

• $1 \leq N \leq 3 \times 10^5$
• $0 \leq A_i \leq N$
• 所有输入值均为整数。

输入

输入以以下格式从标准输入给出：

• $N$
• $A_1$ $A_2$ $\cdots$ $A_N$

输出

输出答案。

3
1 2 0

5

答案为 $5$，即以下 $6$ 个值之和。

• $\mathrm{mex}({A_1}) = \mathrm{mex}({1}) = 0$
• $\mathrm{mex}({A_1,A_2}) = \mathrm{mex}({1,2}) = 0$
• $\mathrm{mex}({A_1,A_2,A_3}) = \mathrm{mex}({1,2,0}) = 3$
• $\mathrm{mex}({A_2}) = \mathrm{mex}({2}) = 0$
• $\mathrm{mex}({A_2,A_3}) = \mathrm{mex}({2,0}) = 1$
• $\mathrm{mex}({A_3}) = \mathrm{mex}({0}) = 1$

6
2 1 0 2 1 4

31

答案为 $31$，即以下 $21$ 个值之和。

• $\mathrm{mex}({A_1}) = \mathrm{mex}({2}) = 0$
• $\mathrm{mex}({A_1,A_2}) = \mathrm{mex}({2,1}) = 0$
• $\mathrm{mex}({A_1,A_2,A_3}) = \mathrm{mex}({2,1,0}) = 3$
• $\mathrm{mex}({A_1,A_2,A_3,A_4}) = \mathrm{mex}({2,1,0,2}) = 3$
• $\mathrm{mex}({A_1,A_2,A_3,A_4,A_5}) = \mathrm{mex}({2,1,0,2,1}) = 3$
• $\mathrm{mex}({A_1,A_2,A_3,A_4,A_5,A_6}) = \mathrm{mex}({2,1,0,2,1,4}) = 3$
• $\mathrm{mex}({A_2}) = \mathrm{mex}({1}) = 0$
• $\mathrm{mex}({A_2,A_3}) = \mathrm{mex}({1,0}) = 2$
• $\mathrm{mex}({A_2,A_3,A_4}) = \mathrm{mex}({1,0,2}) = 3$
• $\mathrm{mex}({A_2,A_3,A_4,A_5}) = \mathrm{mex}({1,0,2,1}) = 3$
• $\mathrm{mex}({A_2,A_3,A_4,A_5,A_6}) = \mathrm{mex}({1,0,2,1,4}) = 3$
• $\mathrm{mex}({A_3}) = \mathrm{mex}({0}) = 1$
• $\mathrm{mex}({A_3,A_4}) = \mathrm{mex}({0,2}) = 1$
• $\mathrm{mex}({A_3,A_4,A_5}) = \mathrm{mex}({0,2,1}) = 3$
• $\mathrm{mex}({A_3,A_4,A_5,A_6}) = \mathrm{mex}({0,2,1,4}) = 3$
• $\mathrm{mex}({A_4}) = \mathrm{mex}({2}) = 0$
• $\mathrm{mex}({A_4,A_5}) = \mathrm{mex}({2,1}) = 0$
• $\mathrm{mex}({A_4,A_5,A_6}) = \mathrm{mex}({2,1,4}) = 0$
• $\mathrm{mex}({A_5}) = \mathrm{mex}({1}) = 0$
• $\mathrm{mex}({A_5,A_6}) = \mathrm{mex}({1,4}) = 0$
• $\mathrm{mex}({A_6}) = \mathrm{mex}({4}) = 0$

25
2 2 1 2 2 0 2 2 2 1 2 2 2 0 2 2 2 2 1 2 2 2 2 0 2

624

• 来源：AtCoder ABC 470 G

子任务设置

• 子任务 1（180 分）：$N \le 2000$。
• 子任务 2（180 分）：$A_i \le 2$。
• 子任务 3（240 分）：无特殊限制。