4487. 高度区间

【题目描述】

想象有 $N$ 列积木，从左到右编号为 $1$ 到 $N$，其中 $N$ 是奇数。第 $i$ 列积木的高度为 $v_i$。特别地，最中间一列（第 $\frac{N+1}{2}$ 列）是最高的一列（或并列最高），设其高度为 $\text{max}$。

现在考虑两个整数 $A$ 和 $B$，满足 $0 \le A < B \le \text{max}$。我们做如下操作：

对于每一列，只保留高度在 $[A, B]$ 范围内的积木（即把高度低于 $A$ 的积木全部拿掉，把高度高于 $B$ 的积木也拿掉）。这样得到一个“截取”后的积木形状。

如果这个截取后的形状关于最中间那一列的竖直中心线是左右对称的，我们就称 $(A,B)$ 是一个好的二元组。

现在有 $Q$ 次修改操作，每次修改某一列的高度（但不会修改最中间那一列，且保证修改后最中间一列仍然是全局最高之一）。对于每一次修改前以及最终状态，请你求出好的二元组 $(A,B)$ 的总数。

大样例

【输入格式】

第一行两个整数 $N, Q$。

第二行 $N$ 个整数 $v_1, v_2, \dots, v_N$。

接下来 $Q$ 行，每行两个整数 $x, h$，表示将第 $x$ 列的高度改为 $h$（保证 $x \neq \frac{N+1}{2}$ 且 $h \le \text{max}$）。

【输出格式】

输出 $Q+1$ 行，每行一个整数，表示对应时刻的好二元组数量。

【样例输入1】

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

【样例输出1】

5
6
1
3
6
36

【样例输入2】

7 0
4 3 1 7 2 3 5

【样例输出2】

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

【样例输出3】

8
8
5
3
3
2
4
4
4
5
7

【样例说明】

对于样例2：

好的二元组为：$(0,1),(2,3),(2,4),(3,4),(5,6),(5,7),(6,7)$，共$7$个。

【数据规模与约定】

本题输入输出量极大，请一定要使用快速读入和快速输出

对于前$20$%的数据，$Q=0$，$N \le 300$，且所有 $v_i \le 300$

对于前$40$%的数据，$Q=0$

对于随后$30$%的数据，每次修改时，该列高度的变化量至多为 $1$

对于$100$%的数据:

- $3 \le N \le 2 \times 10^5$，且 $N$ 为奇数；

- $0 \le Q \le 2 \times 10^5$；

- $0 \le v_i \le 10^6$；

- 任意时刻，中间列 $v_{(N+1)/2}$ 是全局最大值之一；

- 每次修改的列 $x \ne \frac{N+1}{2}$，且修改后的高度 $h \le \text{max}$。