まず、数列ではなく \(1\) つの整数に対して \(A\leftarrow\max\lbrace A,x\rbrace\) およびその取り消しを行うことを考えます。

操作は可換なので、取り消されていない操作に対する \(x\) の値の多重集合をヒープ（いわゆる「消せる priority_queue」）や平衡二分探索木などを用いて管理することで高速に解くことができます。

これを応用してもとの問題を解くことを考えます。

セグメント木のように、\(\lbrack0,N)\) に含まれて \(\lbrack i2 ^ k,(i+1)2 ^ k)\ (i,k\) は整数\()\) の形で書ける \(O(N)\) 個の区間を考えます。 すると、任意の区間 \(\lbrack l,r)\) に対する

• \(A _ i\leftarrow\max\lbrace A _ i,x\rbrace\) と更新する
• その取り消し

の \(2\) つの操作を \(O(\log N)\) 個の多重集合に対する \(x\) の追加および削除として実現することができます。

取得クエリに関しても、\(A _ i\) を含む \(O(\log N)\) 個の多重集合それぞれに含まれる値の最大値をとり、それらの最大値を求めることで \(A _ i\) の値を得ることができます。

時間計算量は適切なデータ構造を用いることで \(O((N+Q)\log N\log Q)\) となります。

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

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <tuple>

int main() {
    using namespace std;

    // 消せる priority_queue に対する操作
    using erasable_priority_queue = pair<priority_queue<unsigned>, priority_queue<unsigned>>;
    // x を追加する関数
    const auto add{[](unsigned x) { return [x](auto &&pq) { return pq.first.push(x); }; }};
    // x を削除する関数
    const auto erase{[](unsigned x) { return [x](auto &&pq) { return pq.second.push(x); }; }};
    // pq に含まれる値の max (空なら 0 ) を返す関数
    const auto top_or_zero{[](auto &&pq) {
        while (!empty(pq.second) && pq.first.top() == pq.second.top()) {
            pq.first.pop();
            pq.second.pop();
        }
        return empty(pq.first) ? 0 : pq.first.top();
    }};

    unsigned N;
    cin >> N;

    vector<erasable_priority_queue> intervals(2 * N);
    for (unsigned i{}, a; i < N; ++i) {
        cin >> a;
        add(a)(intervals[i + N]); // [i, i+1) に対応する区間に a を追加
    }

    // [l, r) を O(log N) 個の区間に分割し、各区間 I に対して callback(I) を呼び出す
    const auto range_update{[N, &intervals](unsigned l, unsigned r, const auto &callback) {
        l += N;
        r += N;
        while (l != r) {
            if (l & 1)
                callback(intervals[l++]);
            if (r & 1)
                callback(intervals[--r]);
            l /= 2;
            r /= 2;
        }
    }};

    // i を含む O(log N) 個の区間を列挙し、各区間 I について mapping(I) を呼び出した結果 m を aggregate(ret, m) で集計する
    const auto point_access{[N, &intervals](unsigned i, const auto &mapping, const auto &aggregate) {
        i += N;
        unsigned ret{};
        while (i) {
            ret = aggregate(ret, mapping(intervals[i]));
            i /= 2;
        }
        return ret;
    }};

    unsigned Q;
    cin >> Q;
    vector<tuple<unsigned, unsigned, unsigned>> instructions(Q);
    for (auto&&[l, r, x] : instructions) {
        unsigned type;
        cin >> type;
        if (type == 1) {
            cin >> l >> r >> x;
            --l;
            range_update(l, r, add(x)); // [l, r) に x を追加
        } else if (type == 2) {
            cin >> x;
            const auto&[l_erased, r_erased, x_erased]{instructions[x - 1]};
            range_update(l_erased, r_erased, erase(x_erased)); // [l_erased, r_erased) から x_erased を削除
        } else {
            cin >> x;
            // 最大値を出力
            cout << point_access(x - 1, top_or_zero, [](auto a, auto b) { return max(a, b); }) << endl;
        }
    }
    return 0;
}