まず、操作がない場合を考えます。 これは青木君が担当する作業コスト（高橋君の仕事のとき \(0\)）の列の累積和を作ることでクエリあたり定数時間で答えを求めることができます。

この問題と答えとの差について考えましょう。 つまり、次の問題を解くことを考えます。

各クエリについて、問題文中の操作をたかだか \(1\) 回行うことで、青木君の作業コストは最大いくつ減少するか求めよ。

仕事 \(i\) が操作の対象になっているとき、青木君の作業コストは以下のように変化します。

• もともと青木君の仕事なら青木君の作業コストは \(P _ i\) 減少する。
• もともと高橋君の仕事なら青木君の作業コストは \(P _ i\) 増加する。

よって、列 \(\overline P _ i\coloneqq{}\)仕事 \(i\) がもともと青木君の仕事のとき \(P _ i\) 、そうでないとき \(-P _ i\ (1\le i\le N)\) を考えると、ある区間に対する操作によって減少する青木君の作業コストは、その区間内の \(\overline P _ i\) の総和になります。

このことから、次の問題が解ければ元の問題が解けることがわかります。

整数列 \(X=(X _ 1,X _ 2,\ldots,X _ N)\) が与えられる。次の形式の質問が \(Q\) 個与えられるので、すべて処理せよ。

• 整数組 \((L,R)\ (1\le L\le R\le N)\) が与えられる。すべての整数組 \((l,r)\ (L\le l\le r\le R)\) にわたる \(\displaystyle\sum _ {i=l} ^ rX _ i\) の最大値を求めよ。

この問題は区間 \([L,R)\) に対して次の \(4\) つの値を管理することで、セグメント木などを用いて計算を行うことができます（セグメント木に乗せるときの簡単さのため、問題設定とは異なり半開区間で計算を行っていることに注意してください）。

• すべての整数組 \((l,r)\ (L\le l\lt r\le R)\) にわたる \(\displaystyle\sum _ {i=l} ^ {r-1}X _ i\) の最大値
• すべての整数 \(r\ (L\lt r\le R)\) にわたる \(\displaystyle\sum _ {i=L} ^ {r-1}X _ i\) の最大値
• すべての整数 \(l\ (L\le l\lt R)\) にわたる \(\displaystyle\sum _ {i=l} ^ {R-1}X _ i\) の最大値
• \(\displaystyle\sum _ {i=L} ^ {R-1}X _ i\) の値

\(X\) の累積和を計算しておくことで管理する値を \(3\) つにすることなどもできます。

時間計算量は \(O(N+Q\log N)\) などになります。

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

#include <iostream>
#include <vector>
#include <ranges>
#include <atcoder/segtree>
using namespace std;

int main() {
    int N, Q;
    cin >> N >> Q;

    vector<pair<bool, int>> task(N);
    for (auto& [S, P] : task) {
        char c;
        cin >> c >> P;
        S = c == 'A';
    }

    // 青木君の作業コストの累積和
    vector<long> task_sum(N + 1);
    for (int i = 0; i < N; ++i) {
        task_sum[i + 1] = task_sum[i] + task[i].second * (task[i].first ? 1 : 0);
    }
    
    // 操作したときに減少する作業コスト
    vector<int> task_diff(N);
    for (int i = 0; i < N; ++i) {
        task_diff[i] = task[i].second * (task[i].first ? 1 : -1);
    }

    // 最大の区間和を求めるセグメント木
    // (答え, 左端を固定, 右端を固定, 両側を固定) を管理する
    atcoder::segtree<tuple<long, long, long, long>, [](auto lhs, auto rhs) {
        auto [ans_l, left_l, right_l, all_l]{lhs};
        auto [r_ans, r_left, r_right, r_all]{rhs};
        return make_tuple(max({ans_l, r_ans, right_l + r_left}), max(left_l, all_l + r_left), max(right_l + r_all, r_right), all_l + r_all);
    }, [] {
        return make_tuple(0L, 0L, 0L, 0L);
    }> segment_tree(task_diff | views::transform([](long x) {
        // 列の要素をセグメント木の要素に変換
        return make_tuple(max(0L, x), max(0L, x), max(0L, x), x);
    }) | ranges::to<vector>());

    for (int i = 0; i < Q; ++i) {
        int L, R;
        cin >> L >> R;
        --L; // 0-indexed 右半開区間にする
        cout << task_sum[R] - task_sum[L] - get<0>(segment_tree.prod(L, R)) << endl;
    }

    return 0;
}