良い列 \(P\) の末尾に良い列 \(Q\) を連結した列 \(P\mathop{+\!\!+}Q\) と等価な良い列は、上記の操作を \(Q\) の先頭から順に行うことで得られます。 これを愚直に行うと \(O(|P||Q|)\) 回操作することになりますが、ソート列のマージと似た要領で先頭の要素から定めていくことで \(O(|P|+|Q|)\) 時間で等価な良い列を得ることができます。

高橋くんが受け取る予定のプレゼントの個数を \(M\) として、\(M\) を相異なる \(2\) べき \(2 ^ {e _ 0}\gt2 ^ {e _ 1}\gt\cdots\gt2 ^ {e _ k}\) の和で表します。 受け取るプレゼントのうち \(\displaystyle\sum _ {0\le i\lt j}2 ^ {e _ i}\) 番目から \(\displaystyle\sum _ {0\le i\le j}2 ^ {e _ j}\) 番目（0-indexed）からなる連続する部分列と等価な良い列を求めておきます。

すると、質問クエリに対しては \(k=O(\log M)\) 個の良い列を順に受け取ったときのテンションの値を求められればよいため \(O\bigl((\log M) ^ 2\bigr)\) 時間で、追加クエリに対しては適切に \(0\) 個以上の列をマージすればよいためならし \(O(\log M)\) 時間で処理ができるようになり、この問題を解くことができました。

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

#include <iostream>
#include <vector>
#include <ranges>
#include <algorithm>

int main() {
    using namespace std;
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    unsigned N;
    long A, B;
    cin >> N >> A >> B;
    vector<long> P(N);
    for (auto&& p : P)
        cin >> p;

    // 良い列の列
    vector<vector<long>> seq;

    // 十分小さい値
    static constexpr long min_sentinel{-800000000000000};

    // 2 つの良い列をマージして等価なひとつの良い列を作る
    const auto merge{[N, A, B](auto&& lhs, auto&& rhs) -> vector<long> {
        const long L(size(lhs)), R(size(rhs));
        vector<long> result;
        result.emplace_back(min_sentinel); // 番兵
        result.reserve(L + R + 1);
        for (long l{}, r{}; l < L || r < R; )
            // 先頭から値を決める
            result.emplace_back(l == L || (r < R && lhs[l] - r * B > rhs[r] - (L - l) * A) ?
                                rhs[r++] - (L - l) * A :
                                max(result.back() + A, lhs[l++] - r * B));
        result.erase(begin(result)); // 番兵を消す
        return result;
    }};

    // 新しい列を追加する
    // 末尾と長さが等しければ、末尾を取り出してマージ
    const auto append_seq{[&seq, &merge](const auto& rec, vector<long>&& p) -> void {
        if (empty(seq) || size(seq.back()) != size(p))
            seq.emplace_back(move(p));
        else {
            auto lhs{move(seq.back())};
            seq.pop_back();
            rec(rec, merge(move(lhs), move(p)));
        }
    }};

    for (const auto p : P)
        append_seq(append_seq, vector{p});

    unsigned Q;
    cin >> Q;

    for (unsigned i{}; i < Q; ++i) {
        unsigned T;
        long X;
        cin >> T >> X;
        if (T == 1)
            append_seq(append_seq, vector{X});
        else {
            for (const auto& s : seq) // 良い列ごとに
                // 二分探索をしてテンションの変化を求める
                X += A * size(s) - (A + B) * *ranges::partition_point(views::iota(0UL, size(s)), [X, &s, B](const long i){
                    return X > s[i] + i * B;
                });
            cout << X << '\n';
        }
    }
    cout << flush;

    return 0;
}