原题传送门
题意：带修维护序列前k大的和
首先性质：1、只关心值；2、k不变
一眼ds，且是排序类的。修改可以拆成插入和删除。一眼Treap。
然后再考虑k不变。我们发现每次修改我们在非前k大的数中其实只关心最大的一个，因为只有它有机会“进化”进入前k大。
所以直接拆成两个，前k大和其余的。
然后因为懒直接multiset不香吗
然后就结束了。
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define ll long long
const int N=500050;
multiset<int>A,B;
int n,k,q,a[N];
ll ans;
inline int read(){
re int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
void print(){
for(multiset<int>::iterator i=A.begin();i!=A.end();i++)cout<<*i<<' ';
puts("");
for(multiset<int>::iterator i=B.begin();i!=B.end();i++)cout<<*i<<' ';
puts("");
}
int main(){
cin>>n>>k>>q;
for(re int i=1;i<=k;i++)A.insert(0);
for(re int i=k+1;i<=n;i++)B.insert(0);
for(re int j=1;j<=q;j++){
int x=read(),y=read();
y=-y;
int val=a[x];
// if(j==6){
// for(re int i=1;i<=n;i++)cout<<a[i]<<' ';
// puts("");
// print();
// }
a[x]=y;
multiset<int>::iterator fnd=A.find(val);
if(fnd!=A.end()){
ans-=val;
A.erase(fnd);
multiset<int>::iterator b=B.begin();
//cout<<"BEGIN="<<*b<<endl;
if(y<=*b){
//puts("star");
ans+=y,A.insert(y);
}
else{
int bg=*b;
A.insert(bg);
ans+=bg;
B.erase(b);
B.insert(y);
}
}
else{
multiset<int>::iterator kp=B.find(val);
if(kp==B.end()){
//puts("star");
//puts("!!!");
}
multiset<int>::iterator p=--A.end();
B.erase(kp);
if(*p<=y){
//puts("star");
B.insert(y);
}
else{
ans-=*p;
B.insert(*p);
A.erase(p);
ans+=y;
A.insert(y);
}
}
//print();
printf("%lld\n",-ans);
//puts("");
}
return 0;
}