如题。知道 $O(n\sqrt{n})$ 过不了，纯粹想练下分块，但是Sub1 过了，sub2和sub3错1~2个点，不知道为什么。。。

注：

1. a数组表示有多少种糖果出现了ai次，并以此分块2. 能不能优化成通过？ 改成了快读，发现好像可以。
2. 得到5RMB的标准是修改我的代码获得60pts，并告诉我哪错了

谢谢大家！

提交link

code:

writer:  houpingze
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(过不了)
PS:\CCF/ \CCF/ \CCF/ \CCF/ \CCF/

*/
/*
Note:

*/
#include <bits/stdc++.h>
#define reg register int
#define INF (1<<30)
#define pb push_back
#define vc vector
#define fst first
#define scd second
//#define int long long
#define rep(i,x,y) for(int i=x;i<=y;i++)
using namespace std;
int read() {
    int res = 0, fs = 1;
    char c = getchar();

    while (!(c >= '0' && c <= '9')) {
        if (c == '-')
            fs = -1;

        c = getchar();
    }

    while (c >= '0' && c <= '9')
        res = res * 10 + c - '0', c = getchar();

    return res * fs;
}
void print(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }

    if (x > 9)
        print(x / 10);

    putchar(x % 10 + '0');
}
int n, cnt, m, ans, tmp, k,a[2000105];
typedef pair<int, int> P;
//struct PROBLEM_SOLVER{
//     int n,m;
//}solver;

//signed main(){
void py() {
    cout << "YES\n";
}

void pn() {
    cout << "NO\n";
} 
int S;
int l[2000005], r[2000005]; 
int id[2000005];
int sum[2000005];
int t[2000005],v[1000005],tt[2000005];
//int notempty
struct node {
    int a, id;
} candy[2000105];
bool cmp(node x, node y) {
    return x.a < y.a;
}
void update(int opt,int x){
//	if(opt==2) opt=-1;
	int su=tt[x];//x糖果有多少个 
	if(opt==1){
		a[su]--;
		v[id[su]]-=su; 
		if(a[su]==0) sum[id[su]]--;
		su++;
//		su=tt[x+1]; 
		
		a[su]++; 
		v[id[su]]+=su;
		tt[x]++;
		if(a[su]==1) sum[id[su]]++;
	}else{
		
		a[su]--;
		v[id[su]]-=su;
		tt[x]--;
		if(a[su]==0) sum[id[su]]--;
		
//		su=tt[x-1]; 
		su--; 
		
		a[su]++;
		v[id[su]]+=su; 
		if(a[su]==1) sum[id[su]]++;
	}
}
int qry(int x){
	int ll=id[x];
	int ans=0;
	for(int i=x;i<=r[ll];i++){
		ans+=a[i]*(i-x);
	}
	for(int i=ll+1;i<=S;i++){
		ans+=v[i]-sum[i]*x;
	}
	return ans;
}
int main() { 
    cin >> n>>m;

    for (int i = 1; i <= n; i++) {
    	candy[i].a=read();
//        cin >> candy[i].a;//有这个糖果  
        tt[candy[i].a]++;//这个糖果有几个 
    }
	for(int i=1;i<=n;i++){ 
//		cout<<t[candy[i].a]<<' ';	 
			a[tt[i]]++;
//			candy[i].a=0;	 
	} 
    S = sqrt(n+m);

    for (int i = 1; i <= S; i++) {
        l[i] = r[i - 1] + 1;
        r[i] = l[i] + S - 1;
    }

    if (r[S] != n+m) {
        S++;
        l[S] = r[S - 1] + 1;
        r[S] = n+m;
    }
    for(int i=1;i<=S;i++){
    	for(int j=l[i];j<=r[i];j++){
    		id[j]=i;
		}
	}
	for(int i=1;i<=n+m;i++){
		v[id[i]]+=a[i]*i;
		if(a[i])
		sum[id[i]]++;
	} 
//	cout<<"ruok";
    rep(aa, 1, m) {
        int opt=read(), l=read();

//        cin >> opt  >> l;
		
		if(opt==1){
			
            update(opt,l);
		}else  if (opt == 2) {
            update(opt,l);
        } else {
            cout << qry(l) << '\n';
        }
    }
    return 0;
}
/*
9 1
1 1 1 2 2 2 4 5 5
*/