专栏文章

题解：AT_abc420_c [ABC420C] Sum of Min Query

违违规用户名1010570
AT_abc420_c题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio5bkq7
此快照首次捕获于
2025/12/02 13:36
3 个月前
此快照最后确认于
2025/12/02 13:36
3 个月前
查看原文

题意

给你一个长度为 NN 的整数序列： AA 和 BB 。
您需要依次处理 QQ 个查询。 每次查询要么得到一个字符 A ,要么得到一个字符 B 。
如果你得到的字符是 A 那么输入 Xi,ViX_i,V_i ，并输出把 AXiA_{X_i} 改为 ViV_i 后 ∑k=1k≤nmin⁡(Ak,Bk)\sum_{k=1}^{k\leq n} \operatorname{min}(A_k,B_k) 。
如果你得到的字符是 B 那么输入 Xi,ViX_i,V_i ，并输出把 BXiB_{X_i} 改为 ViV_i 后 ∑k=1k≤nmin⁡(Ak,Bk)\sum_{k=1}^{k\leq n} \operatorname{min}(A_k,B_k) 。

分析

首先考虑暴力应该怎么做，显然我们只需每次按题目要求修改后，暴力枚举整个 A,BA,B 数组即可。时间复杂度 O(N⋅Q)O(N·Q)。
一个明显的性质，不管你每次做什么操作最多只会使一个位置的 min⁡(Ak,Bk)\operatorname{min}(A_k,B_k) 发生变化。所以我们每次可以在进行操作之前提前预处理出 s=∑k=1k≤nmin⁡(Ak,Bk)s=\sum_{k=1}^{k\leq n} \operatorname{min}(A_k,B_k) 。每次操作时只需让 ss 减去指定位置的 min⁡(Ak,Bk)\operatorname{min}(A_k,B_k) 修改数组值之后再加回 min⁡(Ak,Bk)\operatorname{min}(A_k,B_k) 即可。
形式化的讲:
当更改 AA 数组时让 s−min⁡(AXi,BXi)+min⁡(Vi,BXi)s-\operatorname{min}(A_{X_i},B_{X_i})+\operatorname{min}(V_i,B_{X_i})
更改 BB 数组时让 s−min⁡(AXi,BXi)+min⁡(AXi,Vi)s-\operatorname{min}(A_{X_i},B_{X_i})+\operatorname{min}(A_{X_i},V_i)
时间复杂度 O(N)O(N) 。

代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...