ABC306E题解
CarroT5656
·
·
题解
题目大意
给定一个长度为 N 的序列 A。A 初始每一项都为 0。
有 Q 次操作，每次操作会将 A_x 替换为 Y。
每次操作后，输出 A 中前 K 大的值的和。
解题思路
可以用线段树或平衡树等数据结构来维护。这里介绍一种简便的做法。
首先考虑到每次最多只会改变一个数的值，比较好维护。
开两个 multiset，记为 s 和 s1。
再用一个变量 $cnt$ 记录前 $K$ 大的数的和。
每次操作就从 $s$ 和 $s1$ 中删掉 $A_x$，插入 $Y$。
如果集合中的元素个数不符，那就从另一个集合中搬过来。
时间复杂度 $O(q\log n)$，可以通过。
**Code**
```cpp
#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;
}
```