【map坑点】原始数组为空，有两种操作：1、在数组后面添加元素x 2、复制x个原始数组添加在原始数组后面。q次询问，求第k（k ＜= 1e18)个元素是什么

题目

思路：

隐含条件：第2种操作的次数不会超过log2（1e18）= 64

mp[i] == -1表示有某次第二种操作使数组长度变为i，mp[i] == j(j > 0) 表示第i个位置的元素是j

注意：if(mp[k] > 0) 语句, 如果mp中没有k的键，就会在mp中加一个[k, 0]的键值对

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 5, inf = 1e18;
int a[maxn];
int suf[maxn];
string s;
int n;
map<int, int> mp;
int search(int k)
{
    for (int i = 0; i <= 65; i++)
        {
            if (mp[k] > 0)
            {
                return mp[k];
                break;
            }
            // else if(mp[k] == -1){
            //     auto it = mp.find(k);
            //     it--;
            //     int t = it -> first;
            //     // k = it -> first; 不能这样写
            //     k = (k - 1) % t + 1;
            // }
            else
            {
                mp.erase(k);//因为前面判断语句if(mp[k] > 0)，会在mp中加入[k, 0]的键值对，所以得erase
                auto it = mp.lower_bound(k);
                it--;
                int t = it-> first;
                k = (k - 1) % t + 1;//不能写成k %= t, 因为下标从1开始
                // k %= t;
            }
        }
        return 0;
}
void solve()
{
    mp.clear();
    int k, x, q;
    cin >> n >> q;
    int m = 0;
    for (int i = 1; i <= n; i++)
    {
        int b, x;
        cin >> b >> x;
        if(m >= inf) continue;//inf写成1e18就WA
        if (b == 1)
        {
            mp[++m] = x;
        }
        else
        {
            if(__int128(1 + x) * m > inf) m = inf;//越界了，就改成inf
            else m = (1 + x) * m;
            mp[m] = -1;
        }
    }
    while (q--)
    {
        int k;
        cin >> k;
        cout << search(k) << ' ';
    }
    cout << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}