ABC306E 题解

题目链接

题目大意

维护一个数据结构，数列长度为 \(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;
}