官方题解

题目大意

有一个 $n = 2^{20}$ 大小的数组，其实所有位置都为 $-1$ ，有 $q$ 次操作，每次操作会给出两个整数 $op$ 和 $x$ ，如果 $op=1$ ，则从 $x\%n$ 的位置开始向右寻找第一个为 $-1$ 的位置，找到后将此位置的值设置为 $x$ ；如果 $op=2$ ，则输出数组 $x\%n$ 的值。

解题思路

首先，$n = 2^{20} = 1048576$ ，这是数组可以开到的大小，所以我们可以用数组 $a$ 存储所有位置具体的数字。另外，还可以用 set 存储值为 $-1$ 的位置。

查询时，如果 $op=2$ ，则直接输出 $a[x\%n]$ 即可；如果 $op=1$ ，则可以在 set 中通过二分 lower_bound 函数找到第一个大于等于 $x\%n$ 的位置，如果没找到，则再用二分找第一个大于等于 $0$ 的位置。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 200010;

int main(){
    vector<ll>a(1<<20,-1);
    set<ll>s;
    for(int i=0;i<(1<<20);i++) s.insert(i);
    
    int q;cin>>q;
    while(q--){
        ll op,x;cin>>op>>x;
        ll y=x%(1<<20);
        if(op==2) cout<<a[y]<<endl;
        else{
            auto pos=s.lower_bound(y);
            if(pos==s.end()){
                pos=s.lower_bound(0);
            }

            ll num=*pos;
            a[num]=x;
            s.erase(pos);
        }
    }
    return 0;
}