AT_arc168_f [ARC168F] Up-Down Queries

给定一个长度为 $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 \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 翻译