Description

给定一个长度为n的整数数组A[1]、A[2]、…、AN，和m个操作：

操作1：1 i x 把A[i]的值增加 x （-10^3<=x<=10^3）;

操作2：2 x 查询整数 x 在A[1]..A[N]中出现的次数

Input

第一行包含两个整数n和m，表示数组有n个元素，m表示有m个查询操作；　　接下来的一行包含n个整数，第i个整数表示A[i]；　　再接下来的m行，每行表示一个操作.

Output

按输入顺序输出操作2的结果。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
10 9
3 5 8 17 14 21 7 6 31 5
2 9
1 2 -1
1 1 1
2 4
1 5 2
2 5
1 8 -1
1 2 1
2 5

Sample Output

1
2
3
4
0
2
1
3

分析

用 $Hash$ 来压缩标记数组的空间大小，选取 $Hash$ 的取余数为：$1226959$（网上搜的）
{:.success}

对于每个数 $x$，$x\mod 1226959$ 的值不容易出现重复，因此标记数组开到 $1226959$ 就行了

如果出现重复元素，用 $Vetcor$ 挂邻接表来循环查找即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
#define haha 1226959
#define maxn 1000001
#define gethash(x) (abs(x%haha))
using namespace std;
vector<int> h[haha];
vector<int> g[haha];
int a[maxn];
int n,m;
inline int res(int x){
	int tar=gethash(x);
	vector<int>::iterator iterh=h[tar].begin(); 
	vector<int>::iterator iterg=g[tar].begin();
	while(iterh!=h[tar].end()){
		if(*iterh==x)
			return *iterg;
		iterh++; iterg++;
	}
	return 0;
}
inline void addhash(int x){
	int tar=gethash(x);
	vector<int>::iterator iterh=h[tar].begin(); 
	vector<int>::iterator iterg=g[tar].begin();
	bool exis=false;
	while(iterh!=h[tar].end()){
		if(*iterh==x){
			exis=true;
			(*iterg)++;
			break;
		}
		iterh++; iterg++;
	}
	if(!exis){
		h[tar].push_back(x);
		g[tar].push_back(1);
	}
}
inline void edithash(int p,int v){
	int tar=gethash(p);
	vector<int>::iterator iterh=h[tar].begin(); 
	vector<int>::iterator iterg=g[tar].begin();
	while(iterh!=h[tar].end()){
		if(*iterh==p){
			(*iterg)+=v;break;
		}
		iterh++; iterg++;
	}
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("testin.txt","r",stdin);
	freopen("testout.txt","w",stdout);
	#endif
	cin>>n>>m; int t,d,o;
	for(int i=1;i<=n;i++){
		cin>>a[i]; addhash(a[i]);
	}
	while(m--){
		cin>>o;
		if(o==1){
			cin>>t>>d; edithash(a[t],-1);
			a[t]+=d; addhash(a[t]);
		}else{
			cin>>t;
			cout<<res(t)<<'\n';
		}
	}
	return 0;
}