CF1920D. Array Repetition

思路

用一个数组len记录每次操作后数组的长度，用一个数组lat记录每次操作后数组最后一个数字。对于每次询问，先二分查找出第几次操作能使数组的长度大于等于x

ac代码

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
const i64 inf = 1e18;
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
const int N = 1e6 + 10;

void solve() {
    int n, q;
    cin >> n >> q;
    vector<i64> len(n + 1), lat(n + 1);

    for (int i = 1; i <= n; i++) {
        int op;
        i64 x;
        cin >> op >> x;

        if (op == 1) {
            lat[i] = x;
            len[i] = len[i - 1] + 1;
        } else {
            lat[i] = lat[i - 1];
            if (len[i - 1] != 0) len[i] = len[i - 1] * min(x + 1, inf/len[i - 1] + 1);//查询最长只查到1e18
        }
    }

    auto query = [&](i64 x) {
        while (1) {
            int pos = upper_bound(len.begin() + 1, len.end(), x) - len.begin();
            if (pos == 1) return lat[pos];
            
            x %= len[pos - 1];
            if (x == 0) return lat[pos - 1];
        }
    };

    while (q --) {
        i64 x;
        cin >> x;
        cout << query(x) << ' ';
    }

    cout << endl;

}   

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cout.tie(0);

    int t = 1;
    cin >> t;
    while (t --) solve();

    return 0;
}