We apply a divide-and-conquer algorithm against a sequence.

Let \(f(l,r)\) be the function that finds the answers to all queries contained in an interval \([l,r]\). Calling \(f(1,N)\) yields the answers al the entire queries.

Let \(m=\frac{l+r}{2}\). Queries entirely contained in either \([l, m-1]\) or \([m, r]\) can be recursively handled by \(f(l, m-1)\) and \(f(m r)\), so what we want is the answers to all queries with \(l\leq L_i < m \leq R_i \leq r\).

Define a DP (Dynamic Programming) as follows:

• \(\mathrm{dp}_l(i, j)\ (l\leq i < m)=\) (the maximum total value when choosing items from items \(i\dots m-1\) within a total weight \(j\)),
• \(\mathrm{dp}_r(i, j)\ (m\leq i\leq r)=\) (the maximum total value when choosing items from items \(m\dots i\) within a total weight \(j\)).

The values \(\mathrm{dp}_l\) can be computed in ascending order of \(i\), and \(\mathrm{dp}_r\) in descending order of \(i\), in a total of \(O((r-l)K)\) time (where \(K=\max C_i\)).

Once we evaluate this, the answer to query \(i\) with \(l\leq L_i < m < R_i \leq r\) can be found in \(O(K)\) time as \(\max_{0\leq j\leq C_i} (\mathrm{dp}_l(L+i, j)+\mathrm{dp}_r(R_i,C_i-j))\).

The overall time complexity is \(O(K(Q + N\log N))\). (The complexity of the implementation below is \(O(K(Q + N\log N)+Q\log N)\), but it is possible to get rid of the term \(Q\log N\).)

Sample code (C++):

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int K = 510;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> w(n), v(n);
    for (int i = 0; i < n; i++) {
        cin >> w[i] >> v[i];
    }
    int q;
    cin >> q;
    vector<tuple<int, int, int>> query;
    for (int i = 0; i < q; i++) {
        int l, r, c;
        cin >> l >> r >> c;
        --l;
        query.emplace_back(l, r, c);
    }
    vector<ll> ans(q);
    auto upd_dp = [&](const vector<ll> &dp_pre, vector<ll> &dp_nx, int i) {
        for (int j = 0; j < K; j++) {
            dp_nx[j] = dp_pre[j];
            if (j >= w[i]) {
                dp_nx[j] = max(dp_nx[j], dp_pre[j - w[i]] + v[i]);
            }
        }
    };
    vector dp(n + 1, vector<ll>(K));
    auto f = [&](auto &f, int l, int r, const vector<int> &qid) -> void {
        if (l + 1 == r) {
            for (int i: qid) {
                auto [nl, nr, nc] = query[i];
                assert(nl == l and nr == r);
                ans[i] = (nc >= w[l] ? v[l] : 0);
            }
            return;
        }
        int m = (l + r) / 2;
        fill(dp[m].begin(), dp[m].end(), 0);
        for (int i = m - 1; i >= l; i--) upd_dp(dp[i + 1], dp[i], i);
        for (int i = m + 1; i <= r; i++) upd_dp(dp[i - 1], dp[i], i - 1);
        vector<int> qid_l, qid_r;
        for (int i: qid) {
            auto [nl, nr, nc] = query[i];
            if (nr <= m) {
                qid_l.push_back(i);
            } else if (nl >= m) {
                qid_r.push_back(i);
            } else {
                for (int j = 0; j <= nc; j++) {
                    ans[i] = max(ans[i], dp[nl][j] + dp[nr][nc - j]);
                }
            }
        }
        f(f, l, m, qid_l);
        f(f, m, r, qid_r);
    };
    vector<int> qid(q);
    iota(qid.begin(), qid.end(), 0);
    f(f, 0, n, qid);
    for (int i = 0; i < q; i++) {
        cout << ans[i] << '\n';
    }
}