AT_arc168_f.[ARC168F] Up-Down Queries

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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

准备一个长度为 $M$ $M$ 的整数序列 $y=(y_1,y_2,\cdots,y_M)$ $y = (y_{1}, y_{2}, \dots, y_{M})$ 。初始时， $y$ $y$ 的所有元素均为 $0$ $0$ 。然后，依次对每个 $i=1,2,\cdots,N$ $i = 1, 2, \dots, 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
```
输出#1
```
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

输出#2

输入#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

说明/提示

数据范围

$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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页