哈希表解法

unordered_map清除太慢了，所以手搓了一个（内存爆炸
时间复杂度：$O(q\sqrt n)$

#include <iostream>
#include <cstdio>
#define int long long 
using namespace std;
int a[200005];
int add;
struct node{
	int idx = -1, val = -1;
	node *next = nullptr;
};
struct Hash{
	node *head[505];
	Hash(){
		for(int i = 1; i <= 499; i++){
			head[i] = new node;
		}
	}
	void add(int idx, int val){
		node *p = head[idx % 499 + 1];
		while(p -> next && p -> next -> idx != idx) p = p -> next;//逐个查找
		if(!(p -> next)){//没有就添加一个
			p -> next = new node;
			p = p -> next;
			p -> idx = idx;
			p -> val = val;
		}else p -> next -> val += val;//否则就在原有的加
	}
	int query(int idx){
		node *p = head[idx % 499 + 1];
		while(p -> next && p -> next -> idx != idx) p = p -> next;
		if(!(p -> next)) return 0;
		return p -> next -> val;
	}
	void clear(){
		for(int i = 1; i <= 499; i++){
			if(head[i] -> next) head[i] = new node;//新建一个链表
		}
	}
}mp;
signed main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i], mp.add(i, a[i]);
	int m;
	cin >> m;
	while(m--){
		int tmp;
		cin >> tmp;
		if(tmp == 1){
			int val;
			cin >> val;
			add = val;
			mp.clear();
		}else if(tmp == 2){
			int idx, val;
			cin >> idx >> val;
			mp.add(idx, val);
		}else{
			int idx;
			cin >> idx;
			cout << mp.query(idx) + add << '\n';
		}
	}
	return 0;
}