この問題は \((\)値\(,\) 最後に更新された時間\()\) の組を管理することでも解くことができます。

列 \(S=\big((A _ i,t _ i)\big) _ i\) と組 \(x=(x _ v,x _ t)\) を管理します。 列 \(S\) を \(S=\big((A _ i,0)\big) _ i\) で、\(x\) を \(x=(0,0)\) で初期化しておきます。

処理しているクエリの番号を \(q\) として、クエリごとに次のような処理をすればよいです。

1. \(x\leftarrow(x _ q,q)\) とする。
2. \(t _ {i _ q}\lt x _ t\) なら、\(A _ {i _ q}\leftarrow x _ q\) とする。そうでなければ、\(A _ {i _ q}\leftarrow A _ {i _ q}+x _ q\) とする。そののち、\(t _ {i _ q}\leftarrow q\) とする。
3. \(t _ {i _ q}\lt x _ t\) なら、\(x _ v\) を出力する。そうでなければ、\(A _ {i _ q}+x _ v\) を出力する。

時間計算量は \(O(N+Q)\) です。

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

#include <iostream>
#include <vector>
#include <utility>

int main() {
    using namespace std;

    unsigned N;
    cin >> N;

    // 列を base からの差分と最終更新時刻を管理
    vector<pair<unsigned long, unsigned>> A(N);
    pair<unsigned, unsigned> base{};

    for (auto &&[a, _] : A)cin >> a;
    A.emplace(begin(A));

    unsigned Q;
    cin >> Q;

    for (unsigned q{1}; q <= Q; ++q) {
        unsigned type;
        cin >> type;
        if (type == 1) {
            // base を読み込み、時刻を更新
            cin >> base.first;
            base.second = q;
        } else if (type == 2) {
            // index 番目の差分に加え、時刻を更新
            unsigned index, value;
            cin >> index >> value;
            if (A[index].second < base.second)A[index].first = value;
            else A[index].first += value;
            A[index].second = q;
        } else {
            // base に index 番目の差分を加える
            unsigned index;
            cin >> index;
            if (A[index].second < base.second)cout << base.first << endl;
            else cout << base.first + A[index].first << endl;
        }
    }

    return 0;
}