P16391 [IATI 2024] Game

Klimi and Nikol have an integer array $A$ with $N$ cells numbered from $0$ to $N-1$ and containing $\textbf{different}$ integer values. The girls are playing a game with a single piece that is moved around the array. Initially, the piece is located in some cell. One move of the game proceeds as follows: - The player whose turn it is takes the piece and moves it to another cell that is at distance at most $D$ from the current one. Formally, if the piece is currently in cell $x$ ($0\leq x< N$), then the player is allowed to move the piece to cell $y$ ($0\leq y

The input format of the grader is: - $N$ $D$ - $A_0$ $A_1$ ... $A_{N-1}$ - $Q$ - Where the format of the queries is: - $1$ $\verb|ind|$ $\verb|val|$ --- Update query setting $A_{\mathrm{ind}}=\mathrm{val}$ - $2$ $\verb|ind|$ --- Question query for the piece starting in $\verb|ind|$

For each query of type $2$, the grader will print $0$ if your function returned $\verb|false|$ and $1$ if your function returned $\verb|true|$

### Example Suppose $A = [1, 7, 4, 9, 30, 2]$, $D = 2$, and $Q = 5$. An example sequence of calls is: - Call to $\verb|init({1, 7, 4, 9, 30, 2}, 2)|$ - Call to $\verb|isWinning(0)|$ which returns $\verb|true|$ - Call to $\verb|isWinning(1)|$ which returns $\verb|false|$ - Call to $\verb|updateValue(4, 8)|$ - Call to $\verb|isWinning(0)|$ which returns $\verb|false|$ - Call to $\verb|isWinning(1)|$ which returns $\verb|true|$ The array after the update call is $[1, 7, 4, 9, 8, 2]$. It can be shown that those are the correct answers to the questions if both girls play optimally. ### Constraints - $1 \leq N, Q \leq 2\cdot 10^5$ - $1 \leq D \leq 25$ - $1 \leq A_i \leq 10^9$ - $0 \leq \mathrm{index}, \mathrm{startIndex} < N$ - $1 \leq \mathrm{newValue} \leq 10^9$ - The values in $A$ are all different at all times, including after updates. ### Subtasks | **Subtask** | **Points** | **$N, Q$** | **$D$** | **Extra Constraints** | | :---: | :---: | :---: | :---: | :---: | | $1$ | $8$ | $N, Q \leq 10$ | $D \leq 25$ | | | $2$ | $18$ | $N, Q \leq 2\cdot 10^3$ | $D \leq 25$ | There are no update queries | | $3$ | $16$ | $N, Q \leq 2\cdot 10^5$ | $D \leq 25$ | There are no update queries | | $4$ | $27$ | $N, Q \leq 10^5$ | $D \leq 10$ | | | $5$ | $31$ | $N, Q \leq 2\cdot 10^5$ | $D \leq 25$ | | You must pass all tests in a subtask to get the points.