题解：AT_abc420_c [ABC420C] Sum of Min Query

· · 题解

题意

给你一个长度为 N 的整数序列： A 和 B 。

您需要依次处理 Q 个查询。 每次查询要么得到一个字符 A ,要么得到一个字符 B 。

如果你得到的字符是 A 那么输入 X_i,V_i ，并输出把 A_{X_i} 改为 V_i 后 \sum_{k=1}^{k\leq n} \operatorname{min}(A_k,B_k) 。

如果你得到的字符是 B 那么输入 X_i,V_i ，并输出把 B_{X_i} 改为 V_i 后 \sum_{k=1}^{k\leq n} \operatorname{min}(A_k,B_k) 。

分析

首先考虑暴力应该怎么做，显然我们只需每次按题目要求修改后，暴力枚举整个 A,B 数组即可。时间复杂度 O(N·Q)。

一个明显的性质，不管你每次做什么操作最多只会使一个位置的 \operatorname{min}(A_k,B_k) 发生变化。所以我们每次可以在进行操作之前提前预处理出 s=\sum_{k=1}^{k\leq n} \operatorname{min}(A_k,B_k) 。每次操作时只需让 s 减去指定位置的 \operatorname{min}(A_k,B_k) 修改数组值之后再加回 \operatorname{min}(A_k,B_k) 即可。

形式化的讲:

当更改 A 数组时让 s-\operatorname{min}(A_{X_i},B_{X_i})+\operatorname{min}(V_i,B_{X_i})

更改 B 数组时让 s-\operatorname{min}(A_{X_i},B_{X_i})+\operatorname{min}(A_{X_i},V_i)

时间复杂度 O(N) 。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,sum;
int a[200005];
int b[200005];
int minn[200005];
signed main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        minn[i]=min(a[i],b[i]);
        sum+=minn[i];
    }
    while(q--){
        char op;
        cin>>op;
        int pos,x;
        cin>>pos>>x;
        sum-=min(a[pos],b[pos]);
        if(op=='A'){
            a[pos]=x;
        }
        if(op=='B'){
            b[pos]=x;
        }
        sum+=min(a[pos],b[pos]);
        cout<<sum<<"\n";
    }
    return 0;
}