Codeforces Round 828 (Div. 3) |
---|
Закончено |
Вам дана перестановка $$$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)$$$.
$$$mex$$$ множества чисел $$$S$$$ — это минимальное неотрицательное целое число, которое не встречается в множестве $$$S$$$. Например:
$$$med$$$ множества чисел $$$S$$$ — это медиана множества, то есть элемент, который после сортировки элементов по неубыванию будет стоять на позиции номер $$$\left \lfloor{ \frac{|S| + 1}{2} } \right \rfloor$$$ (элементы массива нумеруются начиная с $$$1$$$ и здесь $$$\left \lfloor{v} \right \rfloor$$$ обозначает округление вниз до наибольшего целого числа, не большего $$$v$$$). Например:
Последовательность из $$$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)$$$.
81021 031 0 240 2 1 353 1 0 2 462 0 4 1 3 583 7 2 6 0 1 5 442 0 1 3
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$$$.
Название |
---|