C++の map<int, int> M は、 i が M に含まれないとき、 M[i]==0 となります。これを利用すると簡潔に解くことができます。

https://atcoder.jp/contests/abc278/editorial/5231 と同様に、 base からの差分で列を管理することにします。 i 番目の差分を M[i] とします。 2のクエリで i が現れていないときは差分が0なので、 M[i]==0 となることは都合が良いです。

• base = 0 、 M[i] = A[i] と初期化します
• 1のクエリでは、 base = x とし、 M を初期化します
• 2のクエリでは、 M[i] += x とします
• 3のクエリでは、 base + M[i] を出力します

M.clear() の計算量はそのときの要素数を \(n\) として \(O(n)\) であり、M に値が追加されうる2のクエリの個数は \(N\) 未満なので、全ての M.clear() の計算量を合計しても \(O(N)\) です。

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main()
{
    int N;
    cin>>N;
    vector<int> A(N);
    for (int &a: A)
        cin>>a;

    int base = 0;
    map<int, long long> M;
    for (int i=0; i<N; i++)
        M[i] = A[i];

    int Q;
    cin>>Q;
    for (int q=0; q<Q; q++)
    {
        int t;
        cin>>t;
        if (t==1)
        {
            int x;
            cin>>x;
            base = x;
            M.clear();
        }
        if (t==2)
        {
            int i, x;
            cin>>i>>x;
            M[i-1] += x;
        }
        if (t==3)
        {
            int i;
            cin>>i;
            cout<<base+M[i-1]<<endl;
        }
    }
}