最初にすべての要素に \(0\) が代入されたと考えて、最後の代入からの差分を保持することを考えます。 与えられるクエリは次のように言い換えられます。

1. これまでの差分をすべて消して \(0\) にし、最後に代入された値を \(x\) に変更する。
2. \(i\) 番目の差分に \(x\) を加える。
3. 最後に代入された値に \(i\) 番目の差分を加え、出力する。

1番目のクエリで差分の値が変わる場所の個数は、直前の代入以降の2番目のクエリの個数を超えません。 よって、「差分が \(0\) でない箇所」を持っておくことで、全体で \(O(N+Q)\) 時間でこの問題を解くことができます。

また、長さ \(N\) の列に区間更新・一点取得を行うセグメント木があれば、それを直接用いることで \(O(N+Q\log N)\) 時間でこの問題を解くことができます（実装例）。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    using namespace std;
    
    unsigned N;
    cin >> N;

    // 列を base からの差分で管理
    vector<unsigned long> A(N);
    unsigned base{};

    for (auto &&a : A)cin >> a;
    A.emplace(begin(A));

    // 差分が 0 でないかもしれない場所
    // はじめは 1, ..., N すべて
    vector<unsigned> added_index(N);
    iota(begin(added_index), end(added_index), 1U);
    
    unsigned Q;
    cin >> Q;

    for (unsigned _{}; _ < Q; ++_) {
        unsigned type;
        cin >> type;
        if (type == 1) {
            // 差分が 0 でないところを消去
            while (!empty(added_index)) {
                A[added_index.back()] = 0;
                added_index.pop_back();
            }
            cin >> base;
        } else if (type == 2) {
            // index 番目の差分に加える
            unsigned index, value;
            cin >> index >> value;
            A[index] += value;
            added_index.emplace_back(index);
        } else {
            // base に index 番目の差分を加える
            unsigned index;
            cin >> index;
            cout << base + A[index] << endl;
        }
    }

    return 0;
}