CF1744F MEX vs MED

给定一个长度为 $n$ 的排列 $p_1, p_2, \ldots, p_n$，排列由 $0, 1, \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$ 表示向下取整）。例如： - $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$），表示测试用例的数量。 接下来是 $t$ 组测试数据。 每组测试数据的第一行包含一个整数 $n$（$1 \leq n \leq 2 \times 10^5$），表示排列 $p$ 的长度。 第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$0 \leq p_i \leq n-1$），表示排列 $p$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一行一个整数，表示满足 $mex(p_l, p_{l+1}, \ldots, p_r) > med(p_l, p_{l+1}, \ldots, p_r)$ 的子区间 $1 \leq l \leq r \leq n$ 的个数。

第一个测试用例只有一个子区间，且 $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$。 由 ChatGPT 4.1 翻译