T2：催化剂

思路

我们能发现，对于每次查找，若有一种糖果类型的糖果数超过 $k$，则它一定会积累最终的答案。

所以，我们需要将每类糖果先给每个小朋友一个，其余的都给一个小朋友即可。

这样一来，问题就转变为了计算：

• $a$ 为糖果数量大于 $k$ 的糖果类型的总糖果数量有多少。
• $b$ 为糖果数量大于 $k$ 的糖果类型的糖果数量之和。
• $k$ 与题意相同。

解题方法

我们使用树状数组进行维护，一个负责找到超过 $k$ 的糖果类型有几个，另一个负责找到超过 $k$ 的糖果类型的总糖果数量有多少。

简单的说，一个在变动时只是 +1 和 -1 的变化，另一个则是 +x 和 -x 的变化。

Code

#include <bits/stdc++.h> 
#define ll long long
using namespace std;
long long n,m;
long long c[1000011*6],a;
ll p[1000011];
ll cs[1000011*6];
long long lowbit(long long x){
	return x&(-x);
}
long long getsun(long long x){
	if(!x) return 0;
	long long sum=0;
	for(long long i=x;i;i-=lowbit(i)) sum+=c[i];
	return sum;
}
void update(long long x,long long y){
	if(!x) return ;
	for(long long i=x;i<=2300000;i+=lowbit(i)){
		c[i]+=y;
	} 
}
long long lowbits(long long x){
	return x&(-x);
}
long long getsuns(long long x){
	if(!x) return 0;
	long long sum=0;
	for(long long i=x;i;i-=lowbits(i)) sum+=cs[i];
	return sum;
}
void updates(long long x,long long y){
	if(!x) return ;
	for(long long i=x;i<=2300000;i+=lowbits(i)){
		cs[i]+=y;
	} 
}
// 直接粘贴，懒
int main(){
	cin >>n >>m;
	for(long long i=1;i<=n;i++){
		ll x;
		scanf("%lld",&x);
		updates(p[x]+1,p[x]+1);
		update(p[x]+1,1);
		updates(p[x],-p[x]);
		update(p[x],-1);
		p[x]++;
	}
	while(m--){
		int op;
		scanf("%d",&op);
		if(op==1){
			long long x;
			scanf("%lld",&x);
			update(p[x]+1,1);
			updates(p[x]+1,p[x]+1);
			update(p[x],-1);
			updates(p[x],-p[x]);
			p[x]++;
		}else if(op==2){
			ll x;
			cin >>x;
			update(p[x],-1);
			updates(p[x],-p[x]);
			update(p[x]-1,1);
			updates(p[x]-1,p[x]-1);
			p[x]--;
		}else{
			long long x;
			scanf("%lld",&x);
			cout <<getsuns(2000000)-getsuns(x)-(getsun(2000000)-getsun(x))*x <<'\n';
		}
	}
	return 0;
}