题目大意

给定一个长度为 $N$ 的序列 $A$。$A$ 初始每一项都为 $0$。

有 $Q$ 次操作，每次操作会将 $A_x$ 替换为 $Y$。

每次操作后，输出 $A$ 中前 $K$ 大的值的和。

解题思路

可以用线段树或平衡树等数据结构来维护。这里介绍一种简便的做法。

首先考虑到每次最多只会改变一个数的值，比较好维护。

开两个 multiset，记为 $s$ 和 $s1$。

$s$ 记录 $A$ 中前 $K$ 大的数，$s1$ 记录前 $N-K$ 小的数。

再用一个变量 $cnt$ 记录前 $K$ 大的数的和。

每次操作就从 $s$ 和 $s1$ 中删掉 $A_x$，插入 $Y$。

如果集合中的元素个数不符，那就从另一个集合中搬过来。

时间复杂度 $O(q\log n)$，可以通过。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ins insert
#define N 500005
ll n,k,q,a[N],ans;
multiset<ll> s,s1;
int main(){
	scanf("%lld%lld%lld",&n,&k,&q);
	for(ll i=1;i<=k;i++) s.ins(0);
	for(ll i=1;i<=n-k;i++) s1.ins(0);
	for(ll i=1,x,y;i<=q;i++){
		scanf("%lld%lld",&x,&y);
		if(s.find(a[x])!=s.end()) s.erase(s.find(a[x])),ans-=a[x];
		else s1.erase(s1.find(a[x]));
		a[x]=y;
		if(s1.size()>0&&y>=*s1.rbegin()) s.ins(y),ans+=y;
		else s1.ins(y);
		if(s.size()<k){
			s.ins(*s1.rbegin());
			ans+=*s1.rbegin();
			s1.erase(s1.find(*s1.rbegin()));
		}
		if(s.size()>k){
			s1.ins(*s.begin());
			ans-=*s.begin();
			s.erase(s.begin());
		}
		printf("%lld\n",ans);
	}
	return 0;
}