Hash | 查询

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

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

0
2
1
3

分析

用 $Hash$ 来压缩标记数组的空间大小,选取 $Hash$ 的取余数为:$1226959$(网上搜的)

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

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

## Code

#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;
}