Sum of Min Query题解

· · 题解

题目大意

给定数组 A\;\;B ，并进行 Q 次操作。

对于每次操作，若第一个值为 A 则将 a_{x} 替换为 y 。

反之将 a_{x} 替换为 y 。

并统计，对于每一次操作 \sum{\min(a_i,b_i)} 的值。

解题思路

首先计算一下时间预期复杂度(内存 1 GB，根本不带怕)

若每次循环时都要遍历一遍 \sum\min(a_i,b_i)，则时间复杂度为 O(nq) 。

该方法遍历次数为 (2\times10^{5})^2，约为 4\times10^{10} 次，超时。

于是我们要思考另一种办法。

考虑到每一次操作只会改变一个值，因此我们只需要定义一个 Res ，输入时累加初值，并在每一次操作中更新他并输出即可，时间复杂度为 O(n+q)。其中 n 的复杂度在于输入，而 q 的复杂度在于查询、更新与输出。

参考代码

附上参考代码

#include<bits/stdc++.h>
using namespace std;
long long n,q,a[200010],b[200010],v[200010],Res;
int main()
{
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%lld",&b[i]),
        Res+=min(a[i],b[i]);
    while(q--)
    {
        char c;
        long long x,y;
        cin>>c>>x>>y;
        long long qq=min(a[x],b[x]);
        if(c=='A')
            a[x]=y;
        else
            b[x]=y;
        Res-=qq-min(a[x],b[x]);
        printf("%lld\n",Res);
    }
    return 0;
}

最后提醒一句，十年OI一场空，不开long long见祖宗
至少我在考场上见祖宗了