AT_abc420_c.[ABC420C] Sum of Min Query

入门

通过率：0%

AC君温馨提醒

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

题目描述

给定长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$ 和 $B=(B_1,B_2,\ldots,B_N)$ 。

你需要依次处理 $Q$ 个查询。第 $i$ 个查询（ $1\le i\le Q$ ）描述如下：

给定一个字符 $c_i$ 和整数 $X_i,V_i$ 。如果 $c_i=$ A，则将 $A_{X_i}$ 修改为 $V_i$ ；如果 $c_i=$ B，则将 $B_{X_i}$ 修改为 $V_i$ 。然后，输出 $\displaystyle \sum_{k=1}^N \min(A_k,B_k)$ 。

输入格式

输入按如下格式给出：

$N$ $Q$
$A_1$ $A_2$ $\ldots$ $A_N$
$B_1$ $B_2$ $\ldots$ $B_N$
$c_1$ $X_1$ $V_1$
$c_2$ $X_2$ $V_2$
$\vdots$
$c_Q$ $X_Q$ $V_Q$

输出格式

输出 $Q$ 行。第 $i$ 行（ $1\le i\le Q$ ）应输出第 $i$ 个查询的答案。

输入输出样例

输入#1

输出#1

7
9
9

输入#2
```
1 3
1
1000000000
A 1 1
A 1 1
A 1 1
```
输出#2
```
1
1
1
```

输入#3

5 3
100 100 100 100 100
100 100 100 100 100
A 4 21
A 2 99
B 4 57

输出#3

421
420
420

说明/提示

样例解释 1

第 1 次查询后， $A=(3,3,4,1),B=(2,7,1,8)$ 。因此，输出 $\min(3,2)+\min(3,7)+\min(4,1)+\min(1,8)=7$ ，输出在第 1 行。

第 2 次查询后， $A=(3,3,4,1),B=(2,7,3,8)$ 。因此，输出 $\min(3,2)+\min(3,7)+\min(4,3)+\min(1,8)=9$ ，输出在第 2 行。

第 3 次查询后， $A=(7,3,4,1),B=(2,7,3,8)$ 。因此，输出 $\min(7,2)+\min(3,7)+\min(4,3)+\min(1,8)=9$ ，输出在第 3 行。

数据范围

$1\le N,Q \le 2 \times 10^5$
$1\le A_i,B_i \le 10^9$
$c_i$ 只可能为 A 或 B
$1\le X_i \le N$
$1\le V_i \le 10^9$
所有输入均为整数。

由 ChatGPT 4.1 翻译

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

首页