愚直に \(A\) を更新すると実行時間に間に合わないため, 陽に \(A\) を更新しない方法をとります.

具体的には, 現時点での \(A\) の長さと, それまでに与えられたクエリ \(1,2\) の情報のみを記録するようにします.
さらにクエリ \(1\) については, そのクエリが与えられた時点でクエリ \(1\) が何個連続していたかを取得できるようにしておきます.

クエリ \(3\) の処理を考えます.
まず \(A\) の長さを管理しているため, 答えが \(-1\) か否かの判定ができます.
また, クエリ処理後の \(x\) 項目がクエリ処理前の何項目であったか, あるいはそのクエリによって追加された項かは \(A\) の具体的な様子が分からなくとも, クエリの情報の記録及び \(x\) の値から求めることができます. 従って, クエリの情報の記録をさかのぼることでクエリ \(3\) の答えを求めることができます.
ただし, クエリ \(1\) の連続した記録についてはまとめてさかのぼるようにします.

計算量を考えます.
\(X=\max x\) とします.
クエリ \(1,2\) の情報及び \(A\) の長さの更新は \(O(1)\) で行えます.
クエリ \(3\) の答えを求めるパートについては, クエリ \(2\) をさかのぼる回数が \(O(\log X)\) 回であり, クエリ \(1\) をまとめてさかのぼるようにしていることから, クエリ \(1,2\) をさかのぼる回数は合計でも \(O(\log X)\) 回です.

よって, 全体で \(O(Q\log X)\) でクエリを処理することができました.

実装例C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {

    int Q;
    cin >> Q;
    ll siz = 1, xmax = ll(1e9 + 1);
    vector<vector<pair<ll, ll>>> query = { {{1,1}} };
    for (int i = 0; i < Q; i++) {
        ll t, x;
        cin >> t >> x;
        if (t == 1) {
            if (query.back()[0].first == 2) {
                query.push_back({});
            }
            query.back().push_back({ 1,x });
            siz = min(xmax, siz + 1);
        }

        else if (t == 2) {
            query.push_back({});
            query.back().push_back({ 2,x });
            siz = min(xmax + 1, siz * 2);
        }

        else {
            if (x > siz) {
                cout << -1 << endl;
                continue;
            }
            ll qn = query.size() - 1, ans;

            while (1) {
                if (query[qn][0].first == 1) {
                    ll d = query[qn].size();
                    if (x > d) x -= d;
                    else {
                        ans = query[qn][d - x].second;
                        break;
                    }
                }
                else {
                    if (x % 2) {
                        ans = query[qn][0].second;
                        break;
                    }
                    else x /= 2;
                }
                qn--;
            }
            cout << ans << "\n";
        }
    }
}