P15582 [KTSC 2026] Balanced Sequence / Balanced Sequence

A **balanced sequence** is defined as follows: - A sequence of length $1$ is a balanced sequence. - A sequence $S = [S_0, \ldots, S_{2k}]$ of length $2k + 1$ is a balanced sequence if and only if: - $[S_0, S_1, \ldots, S_{k-1}]$ is a balanced sequence. - $[S_{k+1}, S_{k+2}, \ldots, S_{2k}]$ is a balanced sequence. - $S_k$ is the **unique** maximum element in $S$. You are given a sequence $A$ of length $N$. Define $A[i \ldots j] = [A_i, A_{i+1}, \ldots, A_j]$. For example, if $A = [3, 5, 7, 2, 9]$, then $A[1 \ldots 3] = [5, 7, 2]$, and $A[4 \ldots 4] = [9]$. There are $Q$ operations, each being a point update. The operations are cumulative. In the initial state and after each operation, compute the number of pairs $(i, j)$ that satisfy: - $0 \le i \le j \le N - 1$. - $A[i \ldots j]$ is a balanced sequence. ### Implementation Details **This is a function-based interactive problem**. You do not need to, and should not, implement the `main` function. You should implement the following functions: ```cpp long long initialize(int N, vector A) ``` - $N$: the length of the sequence $A$. - $A$: an integer array of length $N$. - Return the number of pairs $(i, j)$ such that $0 \le i \le j \le N - 1$ and $A[i \ldots j]$ is a balanced sequence in the initial state. - This function is called exactly once at the start of execution. ```cpp long long update_sequence(int p, int v) ``` - This function represents an operation that sets $A[p] \gets v$. - Return the number of pairs $(i, j)$ such that $0 \le i \le j \le N - 1$ and $A[i \ldots j]$ is a balanced sequence after the operation. - This function is called exactly $Q$ times after `initialize` is called. Your source code must not call any input/output functions.

The input format of the sample grader program is as follows: * Line $1$: $N$ $Q$ * Line $2$: $A[0]$ $A[1]$ ... $A[N-1]$ * For all $1 \le k \le Q$: * Line $2 + k$: $p$ $v$ (the parameters of the $k$-th `update_sequence`)

The sample grader program outputs answers in the following format: * Line $1$: the return value of `initialize` * For all $1 \le k \le Q$: * Line $1 + k$: the return value of the $k$-th `update_sequence`

### Constraints - $1 \le N \le 10^5$. - $0 \le Q \le 10^5$. - $1 \le A[i] \le 10^9$. - $0 \le p \le N - 1$, $1 \le v \le 10^9$. ### Subtasks | ID | Score | Constraints | | :-: | :-: | :- | | $1$ | $3$ | $Q = 0$, $A$ is a balanced sequence | | $2$ | $5$ | $Q = 0$, $A[i] \le 3$ | | $3$ | $12$ | $A[i] \le 3$, $v \le 3$ | | $4$ | $18$ | $Q = 0$, $N \le 2\,000$ | | $5$ | $26$ | $Q \le 10$ | | $6$ | $36$ | No additional constraints | #### Sample 1 Consider the case $N = 4$, $Q = 0$, $A = [1, 1, 1, 1]$. The grader program calls: ```cpp initialize(4, [1, 1, 1, 1]) ``` The pairs $(i, j)$ such that $A[i \dots j]$ is a balanced sequence are $(0, 0)$, $(1, 1)$, $(2, 2)$, $(3, 3)$, so it should return $4$. #### Sample 2 Consider the case $N = 12$, $Q = 0$, $A = [8, 9, 7, 9, 2, 3, 2, 8, 4, 6, 2, 6]$. The grader program calls: ```cpp initialize(12, [8, 9, 7, 9, 2, 3, 2, 8, 4, 6, 2, 6]) ``` The called function returns $18$. #### Sample 3 Consider the case $N = 7$, $Q = 2$, $A = [1, 3, 4, 4, 2, 1, 6]$. The grader program calls the following functions in order: ```cpp initialize(7, [1, 3, 4, 4, 2, 1, 6]) update_sequence(3, 1) update_sequence(3, 2) ``` The called functions return $7$, $9$, and $8$, respectively. Translated by ChatGPT 5