分数: 1100 点
问题陈述
对于整数序列 x=(x_1,x_2,\cdots,x_N) 长度 N 每个元素之间 0 和 M,包含在内,我们定义 f(x) 如下:
- 准备一个整数序列 y=(y_1,y_2,\cdots,y_M) 长度 M。
最初,设置所有元素 y to 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).
给你一个整数序列 A=(A_1,A_2,\cdots,A_N) 长度 N 每个元素之间 0 和 M,包括在内。 工艺流程 Q 查询:
- 的 树的 i-th 查询:给定整数 X_i 和 Y_i,替换值 A_{X_i} 与 Y_i。 然后,打印值 f(A).
约束
- 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
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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
示例输出 1
2 6
考虑第一个查询。 我们将值替换为 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).
接下来,考虑第二个查询。 我们将值替换为 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).
示例输入 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
示例输出 2
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
示例输出 3
1145670 1234421 1352851 1352851 1464137 1380569 1380569 1608611 1724643 1736769