Next and Prev
Contest: Codeforces Round 942 (Div. 1)
Difficulty rating: 3200
Tags: brute force, data structures, implementation

Let $$$p_1, \ldots, p_n$$$ be a permutation of $$$[1, \ldots, n]$$$.

Let the $$$q$$$-subsequence of $$$p$$$ be a permutation of $$$[1, q]$$$, whose elements are in the same relative order as in $$$p_1, \ldots, p_n$$$. That is, we extract all elements not exceeding $$$q$$$ together from $$$p$$$ in the original order, and they make the $$$q$$$-subsequence of $$$p$$$.

For a given array $$$a$$$, let $$$pre(i)$$$ be the largest value satisfying $$$pre(i) < i$$$ and $$$a_{pre(i)} > a_i$$$. If it does not exist, let $$$pre(i) = -10^{100}$$$. Let $$$nxt(i)$$$ be the smallest value satisfying $$$nxt(i) > i$$$ and $$$a_{nxt(i)} > a_i$$$. If it does not exist, let $$$nxt(i) = 10^{100}$$$.

For each $$$q$$$ such that $$$1 \leq q \leq n$$$, let $$$a_1, \ldots, a_q$$$ be the $$$q$$$-subsequence of $$$p$$$. For each $$$i$$$ such that $$$1 \leq i \leq q$$$, $$$pre(i)$$$ and $$$nxt(i)$$$ will be calculated as defined. Then, you will be given some integer values of $$$x$$$, and for each of them you have to calculate $$$\sum\limits_{i=1}^q \min(nxt(i) - pre(i), x)$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1\le t\le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 3\cdot 10^5$$$) — the length of the permutation.

The second line of each test case contains $$$n$$$ integers $$$p_1, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — the initial permutation.

Then, for each $$$q$$$ such that $$$1 \leq q \leq n$$$ in ascending order, you will be given an integer $$$k$$$ ($$$0 \leq k \leq 10^5$$$), representing the number of queries for the $$$q$$$-subsequence. Then $$$k$$$ numbers in a line follow: each of them is the value of $$$x$$$ for a single query ($$$1 \leq x \leq q$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3\cdot 10^5$$$ and the sum of $$$k$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, for each query, print a single line with an integer: the answer to the query.

Constraints:
Time limit: 15.0 s
Memory limit: 1024.0 MB

Note:
The $$$1$$$-subsequence is $$$[1]$$$, and $$$pre=[-10^{100}]$$$, $$$nxt=[10^{100}]$$$. $$$ans(1)=\min(10^{100}-(-10^{100}),1)=1$$$.

The $$$5$$$-subsequence is $$$[1,4,3,2,5]$$$, and $$$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$$$.

Example input:
1
7
6 1 4 3 2 5 7
1 1
0
1 3
1 2
3 1 2 3
1 3
2 2 6

Example output:
1
9
8
5
10
14
16
14
30

Editorial:
Consider an array with length $$$n+x-1$$$. For each integer $$$k$$$ from $$$n$$$ to $$$1$$$, consider $$$i$$$ s.t. $$$p_i = k$$$, we tag the untagged (that is, a position will not be tagged for a second time) positions in the range $$$[i, i + x)\cap \mathbb{Z}$$$. By examining the total number of positions tagged, we have
$$$$$$ \begin{aligned} n + x - 1 &= \sum_{i=1}^n \max(\min(i + x, nxt_i) - \max(pre_i + x, i), 0) \\ &= \sum_{i=1}^n \max(\min(x, nxt_i - i) + \min(i - pre_i, x) - x, 0) \\ &= \sum_{i=1}^n \min(x, nxt_i - i) + \min(i - pre_i, x) -\min(x, \min(x, nxt_i - i) + \min(i - pre_i, x)) \\ &= \sum_{i=1}^n \min(x, nxt_i - i) + \min(i - pre_i, x) - \min(x, nxt_i - pre_i) \\ \end{aligned} $$$$$$
Symmetrically on the other side, we only have to compute $$$\displaystyle \sum_{i=1}^n \min(x, nxt_i - i)$$$. We want to maintain all $$$nxt_i - i$$$ in a sorted order, so that queries can be done using binary search.
This can be done with the help of chunking. Let the length of each block be $$$B$$$. In each block, we divide the positions into two categories: Positions with the maximum $$$nxt_i$$$ (hereinafter referred to as $$$\tt A$$$) and positions without the maximum $$$nxt_i$$$ (hereinafter referred to as $$$\tt B$$$). We sort the positions by $$$nxt_i - i$$$ for A and for B respectively.
How does an update affect the $$$nxt_i - i$$$ values? For the block that the new number is inserted, we brutely reconstruct it. For an affected complete block, the update is $$$+1(nxt_i\gets nxt_i+1)$$$ or $$$\operatorname{chkmin}(nxt_i \gets \min(nxt_i, pos))$$$. A $$$+1$$$ operation can just be handled with a lazy tag.
For a $$$\operatorname{chkmin}$$$ operation, if it only affects the elements with maximum $$$nxt_i$$$, it can be done lazily, otherwise you can reconstruct the whole block.
Let the potential of a block $$$\Phi:= \text{Numbers of different } nxt_i \text{ values in the block}$$$. Similar to the segment tree beats, each insertion increases $$$\sum \Phi$$$ by at most $$$1$$$, and each brute reconstruction takes $$$\mathcal O(B)$$$ time and decreases $$$\sum \Phi$$$ by at least $$$1$$$. Therefore the overall time complexity for the insertion part would be $$$\mathcal O(nB + \frac{n^2}{B})$$$.
To answer a query, we iterate over all the different blocks. If we precalculate the prefix sums of $$$nxt_i - i$$$ in the sorted order, with a simple binary search, this part can be done easily in $$$\mathcal O(\frac{nk\log B}{B})$$$.
Let $$$B = \mathcal O(\sqrt{n})$$$. The time complexity would be $$$\mathcal O(n\sqrt{n} + k\sqrt{n}\log n)$$$, while the space complexity is $$$\mathcal O(n)$$$. Merge sorting or fractional cascading will make the time complexity $$$\mathcal O((n + k)\sqrt{n})$$$, but it runs slower than the previously mentioned solution.