Overview

For each query \([L, R]\), we want to find the minimum total cost of jobs assigned to Aoki A when we are allowed to reverse at most one contiguous subarray within that range.

We express the change in total value caused by a reversal as a “subarray sum,” transforming the problem into efficiently finding the “minimum subarray sum” for each query.

Analysis

First, consider the total cost for Aoki when no operation is performed on query \([L, R]\).

This can be computed in \(O(1)\) by preparing a prefix sum that only adds up costs of A jobs.

Next, consider how Aoki’s total cost changes when we reverse some subarray \([l, r]\).

• Jobs originally assigned to T become A after reversal
  → Aoki’s cost increases by \(+P_i\)
• Jobs originally assigned to A become T after reversal
  → Aoki’s cost decreases by \(-P_i\)

So, for each job \(i\), we define a value \(v_i\) as follows:

\[ v_i = \begin{cases} P_i & (S_i = \mathrm{T}) \\ -P_i & (S_i = \mathrm{A}) \end{cases} \]

Then, the change in Aoki’s total cost when reversing subarray \([l, r]\) is

\[ v_l + v_{l+1} + \cdots + v_r \]

Therefore, the answer for query \([L, R]\) is:

\[ \text{original sum of A costs} + \min(0, \text{minimum subarray sum within } [L, R]) \]

The reason for \(\min(0, \dots)\) is that not performing any operation is also allowed.
If reversing any subarray would only increase the total, then doing nothing is optimal.

---

Naively trying all subarrays within \([L, R]\) for each query takes \(O(N^2)\) in the worst case.
Even computing the minimum subarray sum using Kadane’s algorithm in \(O(R-L+1)\) per query is too slow since \(Q\) can be up to \(10^5\).

Therefore, we use a segment tree to efficiently find the minimum subarray sum over a range.

Algorithm

Each node of the segment tree stores the following \(4\) values for its corresponding interval:

• sum : total sum of the interval
• pref : minimum sum of a non-empty prefix of the interval
• suff : minimum sum of a non-empty suffix of the interval
• best : minimum sum of a non-empty subarray within the interval

For example, consider merging a left interval \(a\) and a right interval \(b\).

The merged sum is simply:

\[ a.sum + b.sum \]

The merged pref is the smaller of:

• A prefix ending within the left interval
• The entire left interval concatenated with a prefix of the right interval

So:

\[ \min(a.pref, a.sum + b.pref) \]

Similarly, suff is:

\[ \min(b.suff, b.sum + a.suff) \]

best, the minimum subarray sum, is the minimum of the following \(3\) patterns:

1. Completely contained within the left interval
2. Completely contained within the right interval
3. A suffix of the left interval concatenated with a prefix of the right interval

Therefore:

\[ \min(a.best, b.best, a.suff + b.pref) \]

With this, the segment tree can compute best for interval \([L, R]\) in \(O(\log N)\).

For each query, we answer as follows:

1. Using the prefix sum of A costs, compute the original total cost for Aoki within \([L, R]\) as base
2. Using the segment tree, find the minimum subarray sum res.best within \([L, R]\)
3. The answer is:

\[ base + \min(0, res.best) \]

Complexity

• Time complexity: \(O((N + Q) \log N)\)
  • Segment tree construction: \(O(N)\)
  • Each query: \(O(\log N)\)
• Space complexity: \(O(N)\)

Implementation Notes

The segment tree handles intervals as half-open intervals \([L, R)\).
Since the input uses \(1\)-indexed closed intervals \([L, R]\), in the implementation we convert as follows:

--L;
query(L, R);

Also, since the operation is performed “at most once,” we do not perform the operation if the minimum subarray sum is positive.
Therefore, the value added to the answer is not res.best itself, but:

min(0LL, res.best)

The identity element for the segment tree is:

Node e{0, INF, INF, INF};

This ensures that an empty interval is never selected as the minimum subarray.

Source Code

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

using ll = long long;

const ll INF = 4000000000000000000LL;

struct Node {
    ll sum;
    ll pref;
    ll suff;
    ll best;
};

Node mergeNode(const Node& a, const Node& b) {
    return {
        a.sum + b.sum,
        min(a.pref, a.sum + b.pref),
        min(b.suff, b.sum + a.suff),
        min({a.best, b.best, a.suff + b.pref})
    };
}

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

    int N, Q;
    cin >> N >> Q;

    int size = 1;
    while (size < N) size <<= 1;

    Node e{0, INF, INF, INF};
    vector<Node> seg(2 * size, e);
    vector<ll> prefA(N + 1, 0);

    for (int i = 0; i < N; i++) {
        char S;
        ll P;
        cin >> S >> P;

        prefA[i + 1] = prefA[i] + (S == 'A' ? P : 0);

        ll v = (S == 'T' ? P : -P);
        seg[size + i] = {v, v, v, v};
    }

    for (int i = size - 1; i >= 1; i--) {
        seg[i] = mergeNode(seg[i << 1], seg[i << 1 | 1]);
    }

    auto query = [&](int l, int r) {
        Node left = e, right = e;
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) left = mergeNode(left, seg[l++]);
            if (r & 1) right = mergeNode(seg[--r], right);
            l >>= 1;
            r >>= 1;
        }

        return mergeNode(left, right);
    };

    while (Q--) {
        int L, R;
        cin >> L >> R;
        --L;

        ll base = prefA[R] - prefA[L];
        Node res = query(L, R);

        cout << base + min(0LL, res.best) << '\n';
    }

    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.