P14379 【MX-S9-T2】「LAOI-16」摩天大楼

> 摩天大楼，太稀有，人人高贵富有；粉饰骷髅，气质有，人们争先恐后。 > > 摩天大楼，想拥有，让人爱不释手；晶莹剔透，攀比后，才能高枕无忧。

Wa1 邀请 ChA 来到一个神秘的二维空间。 这个空间中共矗立着 $n$ 栋摩天大楼，坐标 $i$（$1 \le i \le n$）处矗立着一栋高为 $a_i$ 的摩天大楼。由于该空间的科技水平远超人类，第 $i$ 栋大楼只会阻挡高度**恰好等于** $a_i$ 的飞行物，其他高度的飞行物可以自由通过。 Wa1 为 ChA 准备了一架可飞行于正整数高度的飞机。每次游戏给定起点 $x$ 和终点 $y$（$1 \le x < y \le n$）。Wa1 会选择一个整数 $k$（$x \le k < y$），ChA 只能在第 $k$ 和第 $k+1$ 栋大楼之间改变飞行高度。 为保证安全，ChA 会采用以下策略： - 从起点 $x$ 出发，以**能不改变高度**穿过区间 $[x,k]$ 所有大楼的**最低高度**飞行； - 到达 $k$ 后，如果不是**能不改变高度**穿过区间 $[k+1,y]$ 所有大楼的**最低高度**，再调整到它继续飞行，抵达终点 $y$。 若 ChA 在这次飞行中改变了一次高度，则会消耗 $1$ 单位航油。Wa1 是个卖航油的商人，为了赚取 ChA 的航油费，他会尽量让 ChA 在飞行中必须改变一次高度。 Wa1 邀请 ChA 游玩超值飞行套餐。具体地，设起点和终点为 $x,y$ **最多**耗费 $f(x,y)$ 单位的航油，超值飞行套餐可以让 Wa1 卖出 $\displaystyle \sum_{i=1}^{n}\sum_{j=i+1}^{n}f(i,j)$ 单位的航油。 Wa1 共 $q$ 次邀请 ChA 来游玩超值飞行套餐，第 $i$ 次邀请前他会把 $x_i$ 处的大楼高度修改为 $v_i$。对于每次邀请，Wa1 想知道他能卖出去多少单位航油。

第一行，两个正整数 $n,q$。 第二行，$n$ 个正整数 $a_1, \ldots, a_n$，含义见题目描述。 接下来 $q$ 行，每行两个正整数 $x_i,v_i$，表示第 $x_i$ 栋大楼高度修改为 $v_i$。

共 $q$ 行，每行一个整数，表示答案。

**【样例解释 #1】** 初始高度：$\langle 1, 2, 2, 1, 3\rangle$。 对于第 $1$ 次操作：修改 $a_2 = 1$，新高度为 $\langle 1, 1, 2, 1, 3\rangle$。 - 若相邻两段可通过的最低高度不同，则 ChA 必须升降一次。 - 例如区间 $[1,5]$：选择 $k=2$，则通过 $[1,2]$ 的最低高度为 $2$，通过 $[3,5]$ 的最低高度为 $4$。显然 $2\neq4$，ChA 必须更改一次飞机高度，产生 $1$ 单位的耗油量。 - 统计可得总耗油量为 $9$ 单位。 **【样例 #2】** 见选手目录下的 $\textbf{\textit{building/building2.in}}$ 与 $\textbf{\textit{building/building2.ans}}$。 该样例满足测试点 $1$ 的约束条件。 **【样例 #3】** 见选手目录下的 $\textbf{\textit{building/building3.in}}$ 与 $\textbf{\textit{building/building3.ans}}$。 该样例满足测试点 $4\sim 7$ 的约束条件。 **【样例 #4】** 见选手目录下的 $\textbf{\textit{building/building4.in}}$ 与 $\textbf{\textit{building/building4.ans}}$。 该样例满足测试点 $8$ 的约束条件。 **【样例 #5】** 见选手目录下的 $\textbf{\textit{building/building5.in}}$ 与 $\textbf{\textit{building/building5.ans}}$。 该样例满足测试点 $9, 10$ 的约束条件。 **【样例 #6】** 见选手目录下的 $\textbf{\textit{building/building6.in}}$ 与 $\textbf{\textit{building/building6.ans}}$。 该样例满足测试点 $11, 12$ 的约束条件。 **【样例 #7】** 见选手目录下的 $\textbf{\textit{building/building7.in}}$ 与 $\textbf{\textit{building/building7.ans}}$。 该样例满足测试点 $16\sim 20$ 的约束条件。 **【数据范围】** 本题共 $20$ 个测试点，每个 $5$ 分。 对于所有测试数据，保证： - $2\le n\le 10^6$，$1\le q\le 10^6$； - $1\le x_i\le n$； - $1\le a_i,v_i\le 10^6$。 ::cute-table{tuack} |测试点编号|$n,q\le$|特殊性质| |:--:|:--:|:--:| |$1$|$80$|无| |$2, 3$|$300$|^| |$4\sim 7$|$5\times 10^3$|^| |$8$|$10^6$|A| |$9, 10$|^|B| |$11, 12$|^|C| |$13\sim 15$|^|D| |$16\sim 20$|^|无| 特殊性质 A：任意时刻不存在高度为 $1$ 的大楼。 特殊性质 B：任意时刻高度为 $1$ 的大楼最多存在一个。 特殊性质 C：任意时刻不存在高度为 $2$ 的大楼。 特殊性质 D：$q = 1$。