P15582 [KTSC 2026] 平衡序列 / Balanced Sequence
题目描述
**平衡序列**的定义如下：
- 长度为 $1$ 的序列是平衡序列。
- 长 $2k+1$ 的序列 $S=[S_0,\ldots,S_{2k}]$ 是平衡序列，当且仅当：
- $[S_0,S_1,\ldots,S_{k-1}]$ 是平衡序列；
- $[S_{k+1},S_{k+2},\ldots,S_{2k}]$ 是平衡序列；
- $S_k$ 是 $S$ 中**唯一的**最大元素。
给定长度为 $N$ 的序列 $A$。定义 $A[i\ldots j]=[A_i,A_{i+1},\ldots,A_j]$。例如，若 $A=[3,5,7,2,9]$，则 $A[1\ldots 3]=[5,7,2]$，$A[4\ldots 4]=[9]$。
$Q$ 次操作，每次操作形如单点修改。操作是累积的。在初始状态和每次操作后，求出满足如下条件的 $(i,j)$ 对数：
- $0\le i\le j\le N-1$；
- $A[i\ldots j]$ 是平衡序列。
### 实现细节
**这是一道函数式交互题**。你不必，也不应实现 `main` 函数。
你应当实现以下的函数：
```cpp
long long initialize(int N, vector A)
```
- $N$：序列 $A$ 的长度。
- $A$：长度为 $N$ 的整数数组。
- 返回初始状态下，满足 $0\le i\le j\le N-1$ 且 $A[i\ldots j]$ 为平衡序列的 $(i,j)$ 对数。
- 该函数仅在运行之初被调用恰好一次。
```cpp
long long update_sequence(int p, int v)
```
- 该函数表示一次令 $A[p]\gets v$ 的操作。
- 返回操作后，满足 $0\le i\le j\le N-1$ 且 $A[i\ldots j]$ 为平衡序列的 $(i,j)$ 对数。
- 该函数在 `initialize` 函数调用后，被调用恰好 $Q$ 次。
你的源代码中不应调用任何输入/输出函数。
输入格式
示例评测程序的输入格式如下：
* 第 $1$ 行：$N$ $Q$
* 第 $2$ 行：$A[0]$ $A[1]$ ... $A[N-1]$
* 对于所有 $1 \le k \le Q$：
* 第 $2 + k$ 行：$p$ $v$（第 $k$ 次 `update_sequence` 的参数）
输出格式
示例评测程序按以下格式输出答案：
* 第 $1$ 行：`initialize` 的返回值
* 对于所有 $1 \le k \le Q$：
* 第 $1 + k$ 行：第 $k$ 次 `update_sequence` 的返回值
说明/提示
### 数据范围
- $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$。
### 子任务
| 编号 | 得分 | 限制 |
| :-: | :-: | :- |
| $1$ | $3 $ | $Q=0$，$A$ 是平衡序列 |
| $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$ | 无额外限制 |
#### 样例 1
考虑 $N = 4$, $Q = 0$, $A = [1, 1, 1, 1]$ 的情况。
评测程序调用以下函数：
```cpp
initialize(4, [1, 1, 1, 1])
```
满足 $A[i \dots j]$ 是平衡序列的 $(i, j)$ 有 $(0, 0),(1, 1),(2, 2),(3, 3)$，因此它应该返回 $4$。
#### 样例 2
考虑 $N = 12$, $Q = 0$, $A = [8, 9, 7, 9, 2, 3, 2, 8, 4, 6, 2, 6]$ 的情况。
评测程序调用以下函数：
```cpp
initialize(12, [8, 9, 7, 9, 2, 3, 2, 8, 4, 6, 2, 6])
```
被调用的函数返回 $18$。
#### 样例 3
考虑 $N = 7$, $Q = 2$, $A = [1, 3, 4, 4, 2, 1, 6]$ 的情况。
评测程序按顺序调用以下函数：
```cpp
initialize(7, [1, 3, 4, 4, 2, 1, 6])
update_sequence(3, 1)
update_sequence(3, 2)
```
被调用的函数分别返回 $7, 9, 8$。