提供一种神秘做法（能A）

考场上想出来的神秘做法，具体细节看注释。

时间复杂度：我不到啊 有没有佬能算出来

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=1e5;
ll n,q,x,y;
ll nxt[MAXN],val[MAXN];
//nxt[i]表示i后面第一个空位，val[i]表示i上的数
map<ll,ll> mp;//mp[x]表示数x的位置
int main(){
    cin>>n>>q;
    for(ll i=1;i<n;i++) nxt[i-1]=i;//初始化nxt
    nxt[n-1]=0;
    while(q--){
        cin>>x;
        if(!mp.count(x)){//插入
            y=x%n;//求H(x)
            while(val[y]) y=nxt[y];//按照nxt找到第一个空位
            mp[x]=y;
            val[y]=x;
            nxt[x%n]=(y+1)%n;//更新下一个位置
        }
        cout<<mp[x]<<'\n';
    }
    return 0;
}