线性探查法 - 正经题解

这道题目考的是哈希，那肯定会卡哈希，所以我就不用 unordered_map 做了

本题插入的意思就是找到第一个内容为空的单元，如果直接暴力会被卡到 $O(N)$。

但是，众所又周知，线段树可以 $O(\log N)$ 找到第一个符合条件的点！

那么，模拟，秒了。

诶等等，在样例的第 $4$ 次操作中，由于前面没有空位，它探测到后面去了！

没事，像合并石子一样，再复制一个拼接到后面就能当循环空间用了。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <cmath>
#define int long long
#define double pair <int, int>
using namespace std;
int a[100005];
bool tree[524293];//线段树
int size;
int n, m;
map <int, int> mp;
int get_first(int idx){//O(logN)寻找第一个符合条件的
	if(idx == 0){//线段树不能处理idx=0的情况，得特判
		if(!tree[size]) return 0;
		return get_first(1);
	}
	idx += size;
	do{
		while(~idx & 1) idx >>= 1;
		if(!tree[idx]){
			for(; idx <= size;){
				idx <<= 1;
				if(tree[idx]) idx++;
			}
			return idx - size;
		}
		idx++;
	}while((idx & -idx) != idx);
	return size * 2;
}
void modify(int idx){//O(logN)单点改
	for(tree[idx += size] = 1, idx >>= 1; idx; idx >>= 1){
		tree[idx] = (tree[idx * 2] && tree[idx * 2 + 1]);
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	size = 1 << (int)(ceil(log2(n)) + 1e-5) + 1;
	for(int i = 1; i <= m; i++){
		cin >> a[i];
		if(mp[a[i]]){//如果已经有了就不用修改了
			cout << mp[a[i]] << '\n';
			continue;
		}
		int idx = get_first(a[i] % n);
		if(idx >= n) idx -= n;//循环空间
		modify(idx), modify(idx + n);//修改
		mp[a[i]] = idx;//记录
		cout << idx << '\n';
	}
	

	return 0;
}