哈希表解法
2024-12-31 19:07:51
发布于:广东
29阅读
0回复
0点赞
unordered_map清除太慢了,所以手搓了一个(内存爆炸
时间复杂度:
#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;
}
全部评论 1
厉害
2025-01-01 来自 湖南
0
有帮助,赞一个