P10633 BZOJ2989 Sequence / BZOJ4170 Aurora.

Given a sequence of positive integers $a_i$ of length $n$, the $\text{graze}$ value between two positions is the sum of their position difference and value difference: $\text{graze}(x,y)=|x-y|+|a_x-a_y|$. You must support two types of operations (all $k$ are positive integers): - `Modify x k`, meaning modify the value of the $x$-th number to $k$; - `Query x k`, meaning ask how many $i$ satisfy $\text{graze}(x,i) \leq k$. The query must consider not only the current sequence, but also any historical version. That is, count the number of pairs where any value that has ever appeared at any position and the current $a_x$ has $\text{graze}$ value $\leq k$. (If a position is modified to the same value multiple times, count it multiple times.)

The first line contains two integers $n, q$, representing the sequence length and the number of operations. The second line contains $n$ positive integers, representing the initial sequence. Lines $3$ to $q+2$ each contain one operation.

For each query operation, output one non-negative integer as the answer.

For all testdata, it is guaranteed that $1\leq n\leq 6\times 10^4$, $1\leq$ the number of modify operations $\leq 5\times 10^4$, $1\leq$ the number of queries $\leq 6\times 10^4$, and $1\leq$ the maximum value among all historical versions of $a_i \leq 10^5$. Translated by ChatGPT 5