First, we consider applying and canceling \(A\leftarrow\max\lbrace A,x\rbrace\) against a single integer, instead of a sequence.

Since the operations commute, one can manage the multiset of the values of \(x\) for the operations not canceled so far in a heap (so-called “erasable priority queue” or a balanced binary search tree) to solve it fast.

This idea can be adopted to the original problem too.

As in a segment tree, consider \(O(N)\) segments contained in \(\lbrack0,N)\) and written in the form of \(\lbrack i2 ^ k,(i+1)2 ^ k)\ (i,k\) are integers\()\). Then, for any segment \(\lbrack l,r)\),

• updating \(A _ i\leftarrow\max\lbrace A _ i,x\rbrace\) and
• canceling it

can be realized as addition and removal of \(x\) against \(O(\log N)\) multisets.

The response to a retrieval query of \(A _ i\) can also be found by inspecting the maximum values of the \(O(\log N)\) multisets containing \(A _ i\), and then finding the maximum among them.

The time complexity is \(O((N+Q)\log N\log Q)\), using appropriate data structures.

The sample code is as follows.

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

int main() {
    using namespace std;

    // Operation against erasable priority queue
    using erasable_priority_queue = pair<priority_queue<unsigned>, priority_queue<unsigned>>;
    // Function that adds x
    const auto add{[](unsigned x) { return [x](auto &&pq) { return pq.first.push(x); }; }};
    // Function that deletes x
    const auto erase{[](unsigned x) { return [x](auto &&pq) { return pq.second.push(x); }; }};
    // Function that returns the maximum value in pq (or 0 if empty)
    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]); // Insert a to the segment corresponding to [i, i+1)
    }

    // Split [l, r) into O(log N) segments, and call `callback(I)` for each segment 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) で集計する
    // Enumerate O(log N) segments containing i, and use aggregate(ret, m) to summarize the result m of calling mapping(I) for each segment I
    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)); // Insert x to segment [l, r)
        } 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)); // Remove x_erased from segment [l_erased, r_erased)
        } else {
            cin >> x;
            // Print the maximum value
            cout << point_access(x - 1, top_or_zero, [](auto a, auto b) { return max(a, b); }) << endl;
        }
    }
    return 0;
}