题目描述

给定一个长度为 $N$ 的整数序列 $x=(x_1,x_2,\cdots,x_N)$，其中每个元素满足 $0 \leq x_i \leq M$，定义 $f(x)$ 如下：

• 准备一个长度为 $M$ 的整数序列 $y=(y_1,y_2,\cdots,y_M)$。初始时，$y$ 的所有元素均为 $0$。然后，依次对每个 $i=1,2,\cdots,N$，按顺序进行如下操作：
  • 对于每个整数 $j$（$1 \leq j \leq x_i$），将 $y_j$ 的值替换为 $\max(y_j-1,0)$。
  • 对于每个整数 $j$（$x_i < j \leq M$），将 $y_j$ 的值替换为 $y_j+1$。
• 所有操作结束后，$y$ 的所有元素之和即为 $f(x)$ 的值。

现给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\cdots,A_N)$，其中每个元素满足 $0 \leq A_i \leq M$。请处理 $Q$ 个查询。

• 第 $i$ 个查询：给定整数 $X_i,Y_i$，将 $A_{X_i}$ 的值替换为 $Y_i$，然后输出 $f(A)$ 的值。

输入格式

输入按以下格式从标准输入读入：

$N$ $M$ $Q$
$A_1$ $A_2$ $\cdots$ $A_N$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_Q$ $Y_Q$

输出格式

请输出每次查询后的答案。

样例 1

输入

3 4 2
1 2 3
1 4
3 0

输出

2
6

样例 2

输入

7 2 9
2 0 2 2 0 1 0
1 1
3 0
4 0
4 1
6 1
3 2
2 0
3 2
2 0

输出

4
7
11
9
9
6
6
6
6

样例 3

输入

20 200000 10
39664 143179 193565 153887 16141 91985 51452 155409 116777 190060 87620 64458 106481 51272 9108 100995 139248 18243 181424 6182
4 196305
13 59753
8 96194
6 57037
19 125781
16 142779
15 13967
10 17772
16 84763
12 17283

输出

1145670
1234421
1352851
1352851
1464137
1380569
1380569
1608611
1724643
1736769

说明/提示

数据范围

• $1 \leq N, M, Q \leq 250000$
• $0 \leq A_i \leq M$
• $1 \leq X_i \leq N$
• $0 \leq Y_i \leq M$
• 输入的所有值均为整数。

样例解释 1

首先考虑第 $1$ 个查询。将 $A_1$ 的值替换为 $4$，此时 $A=(4,2,3)$。然后，$f(A)$ 的值按如下方式计算：

• 准备 $y=(0,0,0,0)$。
• 对 $A_1=4$ 进行操作后，$y=(0,0,0,0)$。
• 对 $A_2=2$ 进行操作后，$y=(0,0,1,1)$。
• 对 $A_3=3$ 进行操作后，$y=(0,0,0,2)$。
• $y$ 的元素之和 $=2$，即为 $f(A)$ 的值。

接着考虑第 $2$ 个查询。将 $A_3$ 的值替换为 $0$，此时 $A=(4,2,0)$。然后，$f(A)$ 的值按如下方式计算：

• 准备 $y=(0,0,0,0)$。
• 对 $A_1=4$ 进行操作后，$y=(0,0,0,0)$。
• 对 $A_2=2$ 进行操作后，$y=(0,0,1,1)$。
• 对 $A_3=0$ 进行操作后，$y=(1,1,2,2)$。
• $y$ 的元素之和 $=6$，即为 $f(A)$ 的值。

由 ChatGPT 4.1 翻译