Codeforces Round 942 (Div. 1) |
---|
Закончено |
Пусть $$$p_1, \ldots, p_n$$$ — перестановка массива $$$[1, \ldots, n]$$$.
Пусть $$$q$$$-последовательность $$$p$$$ — это перестановка $$$[1, q]$$$, элементы которой расположены в том же относительном порядке, что и в $$$p_1, \ldots, p_n$$$. То есть мы извлекаем из $$$p$$$ в исходном порядке все элементы, которые не превосходят $$$q$$$, и они составляют $$$q$$$-последовательность $$$p$$$.
Для заданного массива $$$a$$$ пусть $$$pre(i)$$$ — наибольшее значение, удовлетворяющее $$$pre(i) < i$$$ и $$$a_{pre(i)} > a_i$$$. Если такого значения не существует, пусть $$$pre(i) = -10^{100}$$$. Пусть $$$nxt(i)$$$ — наименьшее значение, удовлетворяющее $$$nxt(i) > i$$$ и $$$a_{nxt(i)} > a_i$$$. Если оно не существует, пусть $$$nxt(i) = 10^{100}$$$.
Для каждого $$$q$$$ такого, что $$$1 \leq q \leq n$$$, пусть $$$a_1, \ldots, a_q$$$ — $$$q$$$-последовательность $$$p$$$. Для каждого $$$i$$$, такого, что $$$1 \leq i \leq q$$$, $$$pre(i)$$$ и $$$nxt(i)$$$ будут вычислены в соответствии с условиями выше. Затем вам будут даны некоторые целые значения $$$x$$$, и для каждого из них вы должны вычислить $$$\sum\limits_{i=1}^q \min(nxt(i) - pre(i), x)$$$.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1\le t\le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
В первой строке находится одно целое число $$$n$$$ ($$$1 \leq n \leq 3\cdot 10^5$$$) — длина перестановки.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$p_1, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — начальную перестановку.
Затем, для каждого $$$q$$$ такого, что $$$1 \leq q \leq n$$$, в порядке возрастания, вам будет дано целое число $$$k$$$ ($$$0 \leq k \leq 10^5$$$), представляющее собой количество запросов для $$$q$$$-последовательности. Затем в строке следуют $$$k$$$ чисел: каждое из них является значением $$$x$$$ для одного запроса ($$$1 \leq x \leq q$$$).
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3\cdot 10^5$$$, а сумма $$$k$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Для каждого набора входных данных, для каждого запроса выведите одну строку с целым числом — ответом на запрос.
176 1 4 3 2 5 71 101 31 23 1 2 31 32 2 6
1 9 8 5 10 14 16 14 30
$$$1$$$-последовательность — это $$$[1]$$$, причем $$$pre=[-10^{100}]$$$, $$$nxt=[10^{100}]$$$. $$$ans(1)=\min(10^{100}-(-10^{100}),1)=1$$$.
$$$5$$$-последовательностью является $$$[1,4,3,2,5]$$$, причем $$$pre=[-10^{100},-10^{100},2,3,-10^{100}]$$$, $$$nxt=[2,5,5,5,10^{100}]$$$. $$$ans(1)=5,ans(2)=10,ans(3)=14$$$.
Название |
---|