概要

各問い合わせ \([L, R]\) について、その中の連続区間を高々 \(1\) 回反転したとき、青木君 A が担当する仕事のコスト合計の最小値を求めます。

反転による合計値の変化を「区間和」として表し、各問い合わせで「最小部分区間和」を高速に求める問題に変換します。

考察

まず、問い合わせ \([L, R]\) に対して、何もしない場合の青木君のコスト合計を考えます。

これは、A の仕事のコストだけを足した累積和を用意しておけば、\(O(1)\) で求められます。

次に、ある区間 \([l, r]\) を反転したとき、青木君のコスト合計がどう変わるかを考えます。

• もともと T の仕事は、反転後 A になる
  → 青木君のコストが \(+P_i\) 増える
• もともと A の仕事は、反転後 T になる
  → 青木君のコストが \(-P_i\) 減る

そこで、各仕事 \(i\) に対して値 \(v_i\) を次のように定義します。

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

すると、区間 \([l, r]\) を反転したときの青木君のコスト合計の変化量は

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

になります。

したがって、問い合わせ \([L, R]\) に対する答えは、

\[ \text{もともとの A の合計} + \min(0, \text{区間 } [L, R] \text{ 内の最小部分区間和}) \]

です。

ここで \(\min(0, \dots)\) としているのは、操作をしないことも許されているためです。
もしどの区間を反転しても合計が増えてしまうなら、何もしないのが最適です。

---

素朴に各問い合わせごとに \([L, R]\) 内のすべての区間を試すと、最悪で \(O(N^2)\) かかります。
また、各問い合わせで最小部分区間和を Kadane 法のように \(O(R-L+1)\) で求めても、\(Q\) が最大 \(10^5\) なので間に合いません。

そこで、区間の最小部分区間和を高速に求めるために、セグメント木を使います。

アルゴリズム

セグメント木の各ノードに、対応する区間について次の \(4\) つの値を持たせます。

• sum : 区間全体の和
• pref : 区間の空でない prefix の最小和
• suff : 区間の空でない suffix の最小和
• best : 区間内の空でない部分区間和の最小値

例えば、左区間を \(a\)、右区間を \(b\) として結合する場合を考えます。

結合後の sum は単純に

\[ a.sum + b.sum \]

です。

結合後の pref は、

• 左区間だけで終わる prefix
• 左区間全体に右区間の prefix をつなげるもの

の小さい方なので、

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

です。

同様に suff は、

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

です。

best、つまり最小部分区間和は、次の \(3\) パターンの最小値です。

1. 左区間の中に完全に含まれる
2. 右区間の中に完全に含まれる
3. 左区間の suffix と右区間の prefix をつなげる

したがって、

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

です。

これにより、セグメント木で区間 \([L, R]\) の best を \(O(\log N)\) で求められます。

各問い合わせでは次のように答えます。

1. A のコスト累積和から、元の \([L, R]\) 内の青木君のコスト合計 base を求める
2. セグメント木で \([L, R]\) 内の最小部分区間和 res.best を求める
3. 答えは

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

です。

計算量

• 時間計算量: \(O((N + Q) \log N)\)
  • セグメント木の構築に \(O(N)\)
  • 各問い合わせに \(O(\log N)\)
• 空間計算量: \(O(N)\)

実装のポイント

セグメント木では、区間を半開区間 \([L, R)\) として扱っています。
入力は \(1\) 始まりの閉区間 \([L, R]\) なので、実装では

--L;
query(L, R);

のように変換しています。

また、操作は「高々 \(1\) 回」なので、最小部分区間和が正の場合は操作しません。
そのため、答えに加える値は res.best そのものではなく、

min(0LL, res.best)

になります。

セグメント木の単位元としては、

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

を使います。

これは、空の区間が最小部分区間として選ばれないようにするためです。

ソースコード

#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;
}

---

この解説は gpt-5.5-xhigh によって生成されました。