题目链接
题目大意
维护一个数据结构，数列长度为 \(n\)，\(q\) 次操作，每次操作修改一个位置上的值，每次操作后输出数列里前 \(k\) 小的数的和(\(k\) 是给定的)。
\(n,k,q\leq 5\times 10^5\)
值域 \(1\times 10^9\)
题目分析
开一棵权值线段树，每个节点储存对应区间的数的个数和数的和，然后每次修改直接修改。对于询问，根据区间内数的个数二分出来前若干个线段树上的区间，求和即可。
值域较大，需动态开点。
时间复杂度 $ \mathcal{O}(n+q\log 10^9)$，离散化后可做到 \(\mathcal{O}(n+q\log n)\)。
这个做法可以直接扩展到 \(k\) 是每次询问给定的问题。
参考代码
#include<bits/stdc++.h>
using namespace std;
template<typename T>
void read(T &x){
x=0;
int sgn=0;
char c=getchar();
while(!isdigit(c)) sgn|=(c=='-'),c=getchar();
while(isdigit(c)) x=x*10-'0'+c,c=getchar();
if(sgn) x=-x;
}
typedef long long ll;
const int N=500010,R=1000000001;
struct segment{
struct node{
int ls,rs,cnt;
ll sum;
};
node tr[N<<5];
int idx=1,root=1;
inline void pushup(int u){
tr[u].cnt=tr[tr[u].ls].cnt+tr[tr[u].rs].cnt;
tr[u].sum=tr[tr[u].ls].sum+tr[tr[u].rs].sum;
}
void modify(int u,int l,int r,int pos,int val){
if(l==r){
tr[u].cnt+=val;
tr[u].sum+=val*(l-1);
return ;
}
int mid=(l+r)>>1;
if(pos<=mid){
if(!tr[u].ls) tr[u].ls=++idx;
modify(tr[u].ls,l,mid,pos,val);
}
else{
if(!tr[u].rs) tr[u].rs=++idx;
modify(tr[u].rs,mid+1,r,pos,val);
}
pushup(u);
}
long long query(int u,int l,int r,int k){
if(!u) return 0;
if(l==r) return (l-1)*k;
int mid=(l+r)>>1,s=tr[tr[u].ls].cnt;
if(k>s){
return tr[tr[u].ls].sum+query(tr[u].rs,mid+1,r,k-s);
}
else return query(tr[u].ls,l,mid,k);
}
}sgt;
int n,a[N],k,q;
long long sum=0;
int main(){
read(n),read(k),read(q);
for(int i=1; i<=n; i++) sgt.modify(1,1,R,1,1);
while(q--){
int x,y;
read(x),read(y);
int u=a[x];
a[x]=y;
sum+=(y-u);
sgt.modify(1,1,R,u+1,-1);
sgt.modify(1,1,R,y+1,1);
printf("%lld\n",sum-sgt.query(1,1,R,n-k));
}
return 0;
}