[普及-]A106403.

题意还请自行阅读。

思路

如果直接模拟，每次插入都需要线性探测，当插入位置是连续时，时间复杂度将会退化至 $O(q^2)$，难以接受，考虑其它方法实现或优化。

注意到数组长度为 $2^20 \approx 1e6$，但操作次数 $q \le2 \times 1e5$，因此最大插入 $q$ 个元素，数组有大量空位。
我们可以利用类似并查集的思想来加速找空位的过程。

• 维护一个数组 next，next[i] 表示从位置 $i$ 开始，下一个可能为空位的位置（包括自身）。初始时 next[i] = i。
• 当需要插入时，我们通过 Find(x % n) 找到当前应该插入的空位 $p$，然后：
  1. 将 $a_p$ 设为 $x$。
  2. 将 next[p] 指向下一个可能的空位位置，即 next[(p+1) % n]，表示这个位置已经被占用。
• Find 函数采用路径压缩，使得后续查找更快，均摊复杂度接近 $O(1)$。

查询操作直接输出 $a_{x \bmod n}$ 即可，无需任何额外处理。

#include<bits/stdc++.h>
using namespace std;
const int N = 1 << 20;
int Next[N] , q;
long long val[N];
int G_N(int x){
	return (x + 1) % N;
}
void into(){
	for(int i = 0;i < N;i ++){
		Next[i] = i;
	}
}
int Find(int x){
	if(Next[x] == x){	
        Next[x] = Next[G_N(x)];
		return x;
	}
	return Next[x] = Find(Next[x]);
}
signed main(){
	memset(val , -1 , sizeof(val));
	into();
	cin >> q;
	for(int i = 1;i <= q;i ++){
		int op;
        long long x;
		cin >> op >> x;
		if(op == 1){
			val[Find(x % N)] = x;
		}else{
			cout << val[x % N] << endl;
		}
	}
	return 0;
}