← 返回题目列表

AtCoder · arc168_f

F. 上下查询

中文机器翻译题面 查看原题

分数: 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