← 返回题目列表

Codeforces · 1744/F

F. MEX 与 MED

中文机器翻译题面 查看原题

给你一个排列 $$$p_1, p_2, \ldots, p_n$$$,长度为 $$$n$$$,数字 $$$0, \ldots, n - 1$$$。计算此排列的子段数 $$$1 \leq l \leq r \leq n$$$,使得 $$$mex(p_l, p_{l+1}, \ldots, p_r) > med(p_l, p_{l+1}, \ldots, p_r)$$$。

$$$S$$$ 的 $$$mex$$$ 是 $$$S$$$ 中不出现的最小非负整数。例如:

- $$$mex({0, 1, 2, 3}) = 4$$$
- $$$mex({0, 4, 1, 3}) = 2$$$
- $$$mex({5, 4, 0, 1, 2}) = 3$$$

集合 $$$S$$$ 的 $$$med$$$ 是集合的中位数,即按非降序对元素进行排序后,位于位置号 $$$\left \lfloor{ \frac{|S| 的元素+ 1}{2} } \right \rfloor$$$ (数组元素从 $$$1$$$ 开始编号,这里 $$$\left \lfloor{v} \right \rfloor$$$ 表示向下舍入 $$$v$$$。)。例如:

- $$$med({0, 1, 2, 3}) = 1$$$
- $$$med({0, 4, 1, 3}) = 1$$$
- $$$med({5, 4, 0, 1, 2}) = 2$$$

如果 $$$n$$$ 数字序列包含从 $$$0$$$ 到 $$$n - 1$$$ 的所有数字恰好一次,则该序列称为排列。

输入

输入的第一行包含一个整数 $$$t$$$ $$$(1 \leq t \leq 10^4$$$),即测试用例的数量。

测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$),即排列 $$$p$$$ 的长度。

每个测试用例的第二行恰好包含 $$$n$$$ 整数:$$$p_1, p_2, \ldots, p_n$$$ ($$$0 \leq p_i \leq n - 1$$$),排列元素 $$$p$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,在一行中打印答案:此排列的子段数 $$$1 \leq l \leq r \leq n$$$ 使得 $$$mex(p_l, p_{l+1}, \ldots, p_r) > med(p_l, p_{l+1}, \ldots, p_r)$$$。

示例

输入 #1

8
1
0
2
1 0
3
1 0 2
4
0 2 1 3
5
3 1 0 2 4
6
2 0 4 1 3 5
8
3 7 2 6 0 1 5 4
4
2 0 1 3

输出 #1

1
2
4
4
8
8
15
6

注意

第一个测试用例恰好包含一个子段和 $$$mex({0}) = 1 > med({0}) = 0$$$ 。

在第三个测试用例中,在以下子段上:$$$[1, 0]$$$、$$$[0]$$$、$$$[1, 0, 2]$$$ 和 $$$[0, 2]$$$,$$$mex$$$ 大于 $$$med$$$。

在第四个测试用例中,在以下子段上:$$$[0, 2]$$$、$$$[0]$$$、$$$[0, 2, 1]$$$ 和 $$$[0, 2, 1, 3]$$$、$$$mex$$$ 大于 $$$med$$$。