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

的复杂度在于查询、更新与输出。

参考代码

附上参考代码

CPP

#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见祖宗
~~至少我在考场上见祖宗了~~

文章操作

题目大意

解题思路

参考代码

相关推荐

评论

Sum of Min Query题解