概要

各クエリ \([L,R]\) に対して「区間制約付き 0/1 ナップサック」の最大価値を求める問題です。
\(Q\) が非常に大きいため、各クエリを独立に DP すると間に合わないので、区間の分割統治 + ナップサック DP の前計算で高速化します。

考察

素朴に考えると、各クエリごとに区間 \([L_j,R_j]\) の商品だけで 0/1 ナップサック DP（\(O((R-L+1)M)\)）を行う方法があります。
しかし最悪で \(N=300,\ M=500,\ Q=10^5\) なので、だいたい \(O(QNM)\) となり大きすぎて TLE です。

ここで重要なのは次の2点です。

• \(N\) と \(M\) は比較的小さい（\(300,500\)）
• \(Q\) は非常に大きい（\(10^5\)）

つまり、クエリをまとめて処理する設計が必要です。

分割統治の発想

区間 \([L,R]\) を真ん中 \(mid\) で分けます。
このときクエリは3種類に分かれます：

1. 完全に左側（\(r \le mid\)）→ 左の再帰へ
2. 完全に右側（\(l > mid\)）→ 右の再帰へ
3. \(mid\) をまたぐ（\(l \le mid < r\)）→ その場で回答

またぐクエリを高速に答えるために、以下を前計算します。

• 左側DP：\([i..mid]\) での「予算 \(w\) 以下の最大価値」
• 右側DP：\([mid+1..i]\) での「予算 \(w\) 以下の最大価値」

クエリ \([l,r],X\) がまたぐなら、 - 左部分 \([l..mid]\) のDP配列を \(A\) - 右部分 \([mid+1..r]\) のDP配列を \(B\) として、

[ \max_{0 \le w \le X} \left(A[w] + B[X-w]\right) ]

で答えられます。
これは「予算を左右にどう配るか」を全探索しているだけです。

この方法なら、各クエリは再帰木の各レベルで一度だけ分類され、またぐ瞬間に一度だけマージ計算されます。

アルゴリズム

1. 商品情報 \((H_i,V_i)\) とクエリ \((L_j,R_j,X_j)\) を読む。
2. solve(L,R,qids) を再帰で実行する（qids はこの区間に属するクエリID集合）。
3. 基底：
   • \(L=R\) のとき、その1商品だけ見ればよい。
     予算が足りれば \(V_L\)、足りなければ \(0\)。
4. 中点 \(mid\) を取る。
5. 左DPを構築：
   • i=mid,mid-1,...,L の順に1品ずつ追加する0/1ナップサック。
   • 途中結果を保存しておき、dpl[mid-i] を区間 \([i..mid]\) のDP配列とする。
6. 右DPを構築：
   • i=mid+1,...,R の順に同様。
   • dpr[i-(mid+1)] を区間 \([mid+1..i]\) のDP配列とする。
7. 各クエリを3分類：
   • 左だけ / 右だけ は対応する再帰へ回す。
   • またぐクエリは
     A = dpl[mid-l], B = dpr[r-(mid+1)] を取り、 w=0..X で最大 A[w]+B[X-w] を計算して答えに保存。
8. 左右に再帰。
9. 最後に元の順番で回答を出力。

計算量

• 時間計算量: \(O(NM\log N + QM\log N)\)
  （各再帰ノードでDP構築が区間長\(\times M\)、またぐクエリ処理が1件あたり \(O(M)\)）
• 空間計算量: \(O(NM)\) 程度（再帰の各段で使うDP配列。実装上は都度確保）

実装のポイント

• 価値 \(V_i\) は最大 \(10^9\)、合計はさらに大きくなるので long long を使う。

• 0/1ナップサック更新は for (w=M; w>=H[i]; --w) の逆順で回す。

• dpl[mid-l], dpr[r-(mid+1)] の添字対応を間違えやすいので注意。

• クエリの出力順を保つため、読み込み時に idx を持たせて ans[idx] に書く。

  ソースコード

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

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

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

    vector<int> H(N + 1);
    vector<long long> V(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> H[i] >> V[i];
    }

    // prefix[l][r][w] equivalent storage:
    // leftDP[l][w] = best for items [l..mid]
    // rightDP[r][w] = best for items [mid+1..r]
    // We'll do divide & conquer on index range and answer queries crossing mid.
    struct Query {
        int l, r, x, idx;
    };
    vector<Query> queries(Q);
    for (int i = 0; i < Q; i++) {
        cin >> queries[i].l >> queries[i].r >> queries[i].x;
        queries[i].idx = i;
    }

    vector<long long> ans(Q, 0);

    function<void(int,int,vector<int>&)> solve = [&](int L, int R, vector<int>& qids) {
        if (qids.empty()) return;
        if (L == R) {
            for (int qi : qids) {
                ans[queries[qi].idx] = (queries[qi].x >= H[L] ? V[L] : 0LL);
            }
            return;
        }

        int mid = (L + R) >> 1;

        // Build DP from mid to L
        int leftLen = mid - L + 1;
        vector<vector<long long>> dpl(leftLen, vector<long long>(M + 1, 0));
        {
            vector<long long> cur(M + 1, 0);
            for (int i = mid, t = 0; i >= L; --i, ++t) {
                for (int w = M; w >= H[i]; --w) {
                    cur[w] = max(cur[w], cur[w - H[i]] + V[i]);
                }
                dpl[t] = cur; // corresponds to segment [i..mid]
            }
        }

        // Build DP from mid+1 to R
        int rightLen = R - mid;
        vector<vector<long long>> dpr(rightLen, vector<long long>(M + 1, 0));
        {
            vector<long long> cur(M + 1, 0);
            for (int i = mid + 1, t = 0; i <= R; ++i, ++t) {
                for (int w = M; w >= H[i]; --w) {
                    cur[w] = max(cur[w], cur[w - H[i]] + V[i]);
                }
                dpr[t] = cur; // corresponds to segment [mid+1..i]
            }
        }

        vector<int> leftQ, rightQ;
        leftQ.reserve(qids.size());
        rightQ.reserve(qids.size());

        for (int qi : qids) {
            auto &qq = queries[qi];
            if (qq.r <= mid) {
                leftQ.push_back(qi);
            } else if (qq.l > mid) {
                rightQ.push_back(qi);
            } else {
                // crossing mid: [qq.l..mid] + [mid+1..qq.r]
                const auto &A = dpl[mid - qq.l];
                const auto &B = dpr[qq.r - (mid + 1)];
                int X = qq.x;
                long long best = 0;
                for (int w = 0; w <= X; ++w) {
                    best = max(best, A[w] + B[X - w]);
                }
                ans[qq.idx] = best;
            }
        }

        if (!leftQ.empty()) solve(L, mid, leftQ);
        if (!rightQ.empty()) solve(mid + 1, R, rightQ);
    };

    vector<int> allQ(Q);
    iota(allQ.begin(), allQ.end(), 0);
    solve(1, N, allQ);

    for (int i = 0; i < Q; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

---

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