题目描述

Valentina 刚刚高中毕业，并且今天刚满 18 岁。她正在准备最重要的期末考试：驾驶执照考试。

她在换挡方面有些困难，于是她的哥哥为她准备了一条训练路线。路线由 $N$ 个障碍物组成，第 $i$ 个障碍物必须用指定速度 $a_i$ 通过。

定义一段连续障碍物序列的难度为通过这段序列所需要使用的不同速度数量。例如，对于速度序列

1 2 1 2

它的难度为 $2$。

为了确认自己的驾驶能力，Valentina 每天都会通过路线的每一个可能的连续子段。也就是说，她会通过所有由第 $l$ 到第 $r$ 个障碍物组成的子路线：

$$a_l,a_{l+1},\ldots,a_r \qquad (1\le l\le r\le N).$$

一切本来都很顺利，直到她的“星界双胞胎”Sashka 出现了。Sashka 每天训练结束后都会破坏路线，修改某一个障碍物所需的速度。

Sashka 将进行 $Q$ 次破坏。第 $i$ 次破坏由两个数 $pos$ 和 $x$ 表示，含义是把第 $pos$ 个障碍物的通过速度改为 $x$，即：

$$a_{pos} := x.$$

Valentina 总共会训练 $Q+1$ 天：

• 第 $1$ 天在任何修改发生前训练；
• 第 $2$ 天在第 $1$ 次修改后训练；
• 第 $3$ 天在前 $2$ 次修改后训练；
• ……
• 第 $Q+1$ 天在全部 $Q$ 次修改后训练。

请你对每一天，求所有连续子路线难度之和。

输入格式

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

第二行输入 $N$ 个正整数 $a_1,a_2,\ldots,a_N$。

接下来 $Q$ 行，每行两个整数 $pos,x$，表示一次修改操作：

$$a_{pos}:=x.$$

输出格式

输出 $Q+1$ 行。

第 $i$ 行输出第 $i$ 天训练时，所有连续子路线难度之和。

数据范围

• $1 \le N \le 100000$
• $0 \le Q \le 100000$
• $1 \le a_i,x \le 10^9$
• $1 \le pos \le N$

子任务

子任务	$N$	$Q$	$a_i,x$	其他限制	依赖子任务	分值
1	-			样例	-	0
2	$\le 100$		$\le 200$	-	1	12
3	$\le 1000$		$\le 2000$		1-2	22
4	$\le 100000$	$\le 0$	$\le 2$		-	14
5			$\le 200000$		4	17
6		$\le 100000$			1-5	23
7			$\le 10^9$		1-6	12

只有当某个子任务及其所依赖的子任务全部通过时，才能获得该子任务的分数。

样例 1

输入

3 0
1 2 1

输出

9

样例 2

输入

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

输出

78
74
92
87
82
76
73
55
36

样例 1 解释

所有连续子路线分别为：

(1), (2), (1), (1,2), (2,1), (1,2,1)

它们的难度之和为：

$$1+1+1+2+2+2=9.$$

难度评估

这题需要把“所有子数组不同数个数之和”转化为按数值贡献计数。

对某个值 $v$，它对答案的贡献等于包含至少一个 $v$ 的子数组数量。若 $v$ 出现位置为

$$p_1<p_2<\cdots<p_k,$$

再令 $p_0=0, p_{k+1}=N+1$，则不包含 $v$ 的子数组只会完全落在相邻出现位置之间的空隙中。于是可以维护每个值对应的出现位置集合，并在点修改时只更新旧值和新值的贡献。

难点在于：

• 推出贡献公式；
• 动态维护每个值的有序位置集合；
• 处理 $a_i,x$ 高达 $10^9$ 的值域压缩；
• 细节较多，答案需要 long long。

整体属于比较典型但不低级的动态贡献维护题。

建议 CF 评分：2100。