上位 \(K\) 個が重要なので，それを持っておく． ただし，\(K\) 個の中から追加や削除を行う場合がある．
削除するとき，足りない分を補充しないといけないので， 残りの\(N-K\)個も保存しておく．
削除の際に，配列 \(a\) 自体も持っておく必要がある． 変更前の \(a[x]\) を削除して， 変更後の \(y\) を追加するから．
実装: 追加，削除，調整の3つを用意する． 上位 \(K\) 個の main となるデータ構造と， 残り \(N-K\) 個の sub のデータ構造を考える．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, k, q ;
cin >> n >> k >> q;
vll a(n);
multiset<ll> l,r;
ll s = 0;
auto balance = [&](void) -> void {
if(r.size() < k){
auto it = l.end();
it--;
r.insert(*it);
s += *it;
l.erase(it);
}
if(l.empty() || r.empty()) return;
while(true){
auto itl = l.end(); itl--;
auto itr = r.begin();
if(*itl <= *itr) break;
s += *itl - *itr;
r.insert(*itl);
l.insert(*itr);
// insert したせいで iterator がずれてない
r.erase(itr);
l.erase(itl);
}
};
auto erase = [&](ll v) -> void {
auto it = r.find(v);
if(it != r.end()){
r.erase(it);
s -= v;
}else{
l.erase(l.find(v));
}
balance();
};
auto add = [&](ll v) -> void {
l.insert(v);
balance();
};
rep(i,k) r.insert(0);
rep(i,n-k) l.insert(0);
rep(qi,q){
ll x,y; cin >> x >> y;
--x;
add(y);
erase(a[x]);
a[x] = y;
cout << s << endl;
}
#ifdef _INPUT_
#endif
#ifdef _DEBUG_
#endif
return 0;
}
