P12401 [COI 2025] 玻利维亚 / Bolivija

译自 [COI 2025](https://hsin.hr/hio2025/) T2。 玻利维亚坐落于南美，有着丰富的文化和自然风光。玻利维亚同时也是 IOI 2025 的举办地。 萨哈马火山（Nevado Sajama）是一个复式火山，也是玻利维亚的最高峰，位于玻利维亚奥鲁罗省和萨哈马省的交界处。

考虑一个 $N$ 格的直方图。从左往右数第 $i$ 格的高度为 $v_i$。 这里，$N$ 是奇数，并且 $v_{(N+1)/2}$ 是 $v$ 数组的全局最大值之一。我们令 $\mathrm{mx}=v_{(N+1)/2}$。 对于整数二元组 $(A,B)$ 满足 $0\le A\lt B\le \mathrm{mx}$，我们考虑截取直方图中高度介于 $[A,B]$ 间的部分，如图所示：  如果截取出来的部分关于位于 $(N+1)/2$ 的竖直线是对称的，我们就说 $(A,B)$ 是好的。上图就展示了一个好的 $(A,B)$，这里 $A=2,B=4$。 有 $Q$ 次对 $v$ 数组的单点修改。$\forall 1\le i\le Q+1$，求出在第 $(i-1)$ 次修改后，满足 $\forall 0\le A\lt B\le \mathrm{mx}$ 的二元组 $(A,B)$ 中，有多少个二元组是好的。 我们保证修改不会破坏「$v_{(N+1)/2}$ 是数组全局最大值之一」的性质。

第一行，两个非负整数 $N,Q$。 第二行，$N$ 个非负整数 $v_1,v_2,\ldots,v_N$。 接下来 $Q$ 行，每行两个非负整数 $x,h$，描述一次修改 $v_{x}\gets h$。 保证 $x\neq (N+1)/2$，且 $h\le \mathrm{mx}$。

输出 $(Q+1)$ 行，第 $i$ 仅一个非负整数，第 $(i-1)$ 次修改后的答案。

### 样例解释 #### 样例 $2$ 解释 样例 $2$ 对应的图片即为【题面描述】中的图片。 好的二元组为：$(0, 1), (2, 3), (2, 4), (3, 4), (5, 6), (5, 7), (6, 7)$，共 $7$ 个。 ### 数据范围 - $3\le N\le 2\times 10^5$，且 $N$ 为奇数； - $0\le Q\le 2\times 10^5$； - $v_i\le 654\, 200$（萨哈马火山的高度为 $654200\,\mathrm{cm}$）； - 在任意时刻，$v_{(N+1)/2}$ 是 $v $ 的一个最大值； - $x\neq (N+1)/2$。 ### 子任务 - $\text{Subtask 0 (0 pts)}$：样例。 - $\text{Subtask 1 (9 pts)}$：$Q=0,N\le 300,v_i\le 300$。 - $\text{Subtask 2 (23 pts)}$：$Q=0$。 - $\text{Subtask 3 (31 pts)}$：每次修改，$v_i$ 的值变化至多为 $1$。 - $\text{Subtask 4 (37 pts)}$：无额外约束。