题目描述

平衡序列的定义如下：

• 长度为 $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 函数。

你应当实现以下的函数：

long long initialize(int N, vector<int> A)

• $N$：序列 $A$ 的长度。
• $A$：长度为 $N$ 的整数数组。
• 返回初始状态下，满足 $0\le i\le j\le N-1$ 且 $A[i\ldots j]$ 为平衡序列的 $(i,j)$ 对数。
• 该函数仅在运行之初被调用恰好一次。

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 的返回值

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

提示

数据范围

• $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]$ 的情况。 评测程序调用以下函数：

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]$ 的情况。 评测程序调用以下函数：

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]$ 的情况。 评测程序按顺序调用以下函数：

initialize(7, [1, 3, 4, 4, 2, 1, 6])
update_sequence(3, 1)
update_sequence(3, 2)

被调用的函数分别返回 $7, 9, 8$。