Problem Description

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:

long long initialize(int N, vector<int> 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.

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.

Input Format

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)

Output Format

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

4 0
1 1 1 1

4

12 0
8 9 7 9 2 3 2 8 4 6 2 6

18

7 2
1 3 4 4 2 1 6
3 1
3 2

7
9
8

Hint

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

Sample 1

Consider the case $N = 4$, $Q = 0$, $A = [1, 1, 1, 1]$. The grader program calls:

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:

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:

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