公式解説

各 $P_i$ の長さを $i$ の昇順に並べた数列 $T$ を考えると、両クエリは次のように言い換えられます。
タスク 1： $T_{L_j}, T_{L_j + 1}, ..., T_{R_j}$ に $X_j$ を加算する。
タスク 2： $T_{A_j}, T_{A_j + 1}, ..., T_{B_j}$ の最大値を取得する。
これらを愚直に行うと、時間計算量が $O(ND)$ になってしまいますが、遅延伝播セグメント木を使うと高速に（時間計算量 $O(N + D \log N)$ で）行えます。
遅延伝播セグメント木は AtCoder Library にもあるので、データ構造そのものを実装する必要はここではありません。
参考サイト： https://betrue12.hateblo.jp/entry/2020/09/22/194541

解答 (C++)

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;

using ll = long long;

using S = ll;
S op(S a, S b) { return max(a, b); }
S e() { return 0; }
using F = ll;
S mapping(F f, S x) { return f + x; }
F composition(F f, F g) { return f + g; }
F id() { return 0; }

int main() {
    int n; cin >> n;
    vector<ll> h(n); for (auto& k : h) cin >> k;
    int d; cin >> d;
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(h);
    for (int _ = 0; _ < d; _++) {
        int l, r, a, b; ll x;
        cin >> l >> r >> x >> a >> b;
        --l; --a;
        seg.apply(l, r, x);
        cout << seg.prod(a, b) << endl;
    }
}
Copy