P10673

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[2000005];
struct node{
	int left,right,sum,cnt;
}tree[8000005];
void pushup(int x){
	tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;
	tree[x].cnt=tree[x<<1].cnt+tree[x<<1|1].cnt;
}
void build(int x,int l,int r){
	tree[x].left=l;
	tree[x].right=r;
	if(l==r){
		tree[x].sum=a[l]*l;
		tree[x].cnt=a[l];
		return ;
	} 
	int mid=(l+r)>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	pushup(x);
}
void update(int x,int p){
	if(tree[x].left==tree[x].right){
		tree[x].sum=a[tree[x].left]*tree[x].left;
		tree[x].cnt=a[tree[x].left];
		return ;
	}
	int mid=(tree[x].left+tree[x].right)>>1;
	if(p<=mid){
		update(x<<1,p);
	}
	else{
		update(x<<1|1,p);
	}
	pushup(x);
}
int query(int x,int l,int r,int c){
	if(l<=tree[x].left&&r>=tree[x].right){
		//cout<<x<<" "<<tree[x].sum-c*tree[x].cnt<<" "<<tree[x].left<<" "<<tree[x].right<<endl;
		return tree[x].sum-c*tree[x].cnt;
	}
	int mid=(tree[x].left+tree[x].right)>>1;
	int ans=0;
	if(l<=mid){
		ans+=query(x<<1,l,r,c);
	}
	if(r>mid){
		ans+=query(x<<1|1,l,r,c);
	}
	return ans;
}
int b[2000005];
signed main(){
	int n,q;
	scanf("%lld%lld",&n,&q);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%lld",&x);
		b[x]++;
	}
	for(int i=1;i<=n;i++){
		a[b[i]]++;
	}
	build(1,1,n);
	while(q--){
		int opt,x;
		scanf("%lld%lld",&opt,&x);
		if(opt==1){
			a[b[x]]--;
			update(1,b[x]);
			b[x]++;
			a[b[x]]++; 
			update(1,b[x]);
		}
		if(opt==2){
			a[b[x]]--;
			update(1,b[x]);
			b[x]--;
			a[b[x]]++;
			update(1,b[x]);
		} 
		if(opt==3){
			printf("%lld\n",query(1,x+1,n,x));
		}
	} 
	return 0;
}