P6107 [Ynoi2010] Worst Case Top Tree

Given a sequence $a_0,a_1,a_2,\dots,a_n,a_{n+1}$. It satisfies $a_0=a_{n+1}=+\infty$, and $a_1,a_2,\dots,a_n$ are given in the input. For $1 \le x \le n$, define that $\max_{0 \le i < x, a_i \ge a_x} i$ and $x$ are **adjacent**, and $\min_{x < i \le n+1, a_i > a_x} i$ and $x$ are **adjacent**. If $x$ and $y$ are adjacent, then $y$ and $x$ are also adjacent. If $0 \le b_1,b_2,b_3,b_4,b_5,b_6 \le n+1$, and $b_i$ is adjacent to $b_{i+1}$, $b_1$ is adjacent to $b_6$, and all $b_i$ are distinct, then the set $\{b_1,b_2,b_3,b_4,b_5,b_6\}$ is called a 6-cycle (that is, when judging whether two 6-cycles are the same, the order of $b_i$ is not considered). There are $m$ modification operations. Each operation gives $x\;y$, and changes $a_x$ to $a_x+y$. After each modification, you need to output the number of 6-cycles.

The first line contains an integer $n$. The second line contains $n$ integers $a_1\;a_2\;\dots\;a_n$. The third line contains an integer $m$. The next $m$ lines each contain two integers $x\;y$, describing one modification operation.

Output $m$ lines. Each line contains one integer, the number of 6-cycles after each modification.

Idea: ccz181078, Solution: ccz181078, Code: ccz181078&zx2003, Data: nzhtl1477&zx2003. For $100\%$ of the testdata, all values mentioned above are integers, and $1 \le n,m \le 5 \cdot 10^5;\;1 \le x \le n;\;1 \le a_i,y \le 10^9$. Translated by ChatGPT 5