题解：AT_abc420_c [ABC420C] Sum of Min Query

· · 题解

给定两个长度为 N 的整数序列 A 和 B。需要处理 Q 个查询。每个查询给出一个字符 c_i 和两个整数 X_i,V_i。如果 c_i 是 A，则将 A_{X_i} 修改为 V_i；如果 c_i 是 B，则将 B_{X_i} 修改为 V_i。每次修改后计算并输出 \sum_{k=1}^{N} \min(A_k, B_k)。1≤N,Q≤2×10^5，1≤A_i,B_i,V_i≤10^9，1≤X_i≤N。

C 题犯了个下标错误导致被罚了 10 min。

C 题不难，但朴素暴力会达到 O(Q\times N)，这显然不行。我们只需要一点思维就可以优化至 O(N+Q)。
我们先初始化一个 min 使 min=\sum_{k=1}^{N} \min(A_k, B_k)。那么对于每次修改，我们只需要先将 min 减 \min(A_x,B_x)，再根据 c 修改 A_x 或 B_x 的值，最后再让 min 增加 \min(A_x,B_x) 即可。

C++通过代码。