5524. 「COI 2025」Bolivija

---

题目描述

译自 COI 2025 T2「Bolivija」

玻利维亚，一个美丽的南美国家，拥有丰富的文化和历史，充满了自然美景，包括部分亚马逊雨林和安第斯山脉。对我们的参赛者更重要的是，这里是下一届国际信息学奥林匹克竞赛的举办地！

作为竞赛宣传的一部分，组织者们接到了一个任务：拍摄山脉并制作一本包含最令人惊叹的照片的相册。我们将山脉表示为一个由 $N$ 个非负整数组成的序列 $v$，这些整数依次代表山脉中群山的高度。其中，$N$ 是奇数，且中心的山峰（位于位置 $\frac{N+1}{2}$）正是最高的，其顶峰是内瓦多·萨哈马死火山。

组织者们对收集照片有非常具体的要求。首先，他们选择两个非负整数 $A$ 和 $B$，使得 $A < B$，并且 $B$ 小于或等于最高峰内瓦多·萨哈马的高度。然后，他们调整照片的取景框，使其宽度覆盖所有 $N$ 座山，但照片只包含高度在 $A$ 和 $B$ 之间的部分。此外，只有当照片关于穿过中心山峰的对称轴对称时，组织者们才会对这张照片感到满意。

对应第二个样例的有效照片选择示例如下：

现在，组织者们想知道他们能收集到多少张不同的照片，也就是说，有多少对满足条件的数字 $A$ 和 $B$。在他们为答案思考了太久之后，剧烈的构造活动导致一些山的高度发生了变化。总共发生了 $Q$ 次高度变化，你的任务是帮助组织者们确定每次变化后所求的照片数量。在此过程中，没有任何一次变化影响到中心山峰的高度，并且它在任何时候都是最高的山峰。

---

输入格式

第一行是自然数 $N$ 和 $Q$，分别代表山的总数和变化的次数。

第二行是一个由 $N$ 个非负整数组成的序列 $v$，依次是山脉中群山的高度。保证 $N$ 是奇数，且中心的山峰正是最高的。

在接下来的 $Q$ 行中，第 $i$ 行是自然数和非负整数 $x_{i}$ 和 $h_{i}$ $(1 \leq x_{i} \leq N)$，表示位置 $x_{i}$ 上的山的高度变为新的高度 $h_{i}$。保证 $x_{i} \neq \frac{N+1}{2}$，且新的高度小于或等于中心山峰的高度。

---

输出格式

输出 $Q+1$ 行。在第 $i$ 行，输出经过 $i-1$ 次构造变化后可能的照片数量。

---

样例 1

输入

5 5
1 5 8 7 3
1 8
4 1
2 0
4 0
5 8

输出

5
6
1
3
6
36

---

样例 2

输入

7 0
4 3 1 7 2 3 5

输出

7

---

样例 3

输入

7 10
1 6 7 10 5 4 3
2 7
2 8
2 9
2 9
2 10
6 5
6 6
6 7
6 8
6 9

输出

8
8
5
3
3
2
4
4
4
5
7

---

数据范围与提示

对于所有输入数据，满足 $3 \leq N \leq 200000$ 且 $0 \leq Q \leq 200000$。

对于所有 $i=1, \ldots, N$，满足 $v_{i} \leq 654200$（内瓦多·萨哈马峰顶的高度，单位：厘米）。

子任务

子任务	分值	附加限制
1	9	$Q=0$, $N \leq 300$，且对于所有 $i=1, \ldots, N$ 都有 $v_{i} \leq 300$
2	23	$Q=0$
3	31	每次变化最多使山的高度改变 $1$
4	37	无附加限制