题面稍微有一点不一样。
Statement
给 \(n\) 个物品，每个物品有价值 \(v_i\)、体积 \(w_i\)。
\(q\) 次询问，问考虑 \([L..R]\) 区间的物品，用容量为 \(m\) 的背包最多能装多少价值的物品，有多少种方案，每个物品只能被装一次。
\(n\le 2\cdot 10^4, q\le 10^5, w_i,m_i\le 500, v_i\le 10^6\).
Solution
离线下来猫树分治。每次对于分治区间 \([l..r]\)，回答所有跨过 \(mid\) 的询问。
如果我们知道两个“至多”的 01 背包数组，就可以 \(O(m)\) 每次回答。
如何处理出两个“至多”的 01 背包数组呢？在处理“恰好”的数组的同时对前一个取 max。
Code
不保证输入输出格式正确。
// 没卡常
#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
typedef long long ll;
const int N = 20010, Q = 100010, M = 510, P = 998244353, INF = 1e9;
int n, m, q;
struct Item {
int v, w;
} a[N];
struct Queries {
int l, r, m, id;
} qq[Q];
pair<int, int> ans[Q];
int LF[N][M], LG[N][M], RF[N][M], RG[N][M];
int Max[N][M], MxSumG[N][M];
void Solve(int l, int r, vector<int> & vec) {
if (l > r) return;
if (l == r) {
for (int id : vec) {
auto & now = qq[id];
if (now.m < a[l].w) ans[now.id] = make_pair(0, 0);
else ans[now.id] = make_pair(a[l].v, 1);
}
return;
}
int mid = (l + r) >> 1;
rep(i, l - 1, r + 1) {
rep(j, 0, m) LF[i][j] = RF[i][j] = -INF, LG[i][j] = RG[i][j] = 0;
LF[i][0] = RF[i][0] = 0, LG[i][0] = RG[i][0] = 1;
}
reo(i, mid, l) {
rep(j, 0, m) {
LF[i][j] = LF[i + 1][j];
LG[i][j] = LG[i + 1][j];
}
reo(j, m, a[i].w) {
int Value = LF[i][j - a[i].w] + a[i].v;
if (Value > LF[i][j]) LF[i][j] = Value, LG[i][j] = LG[i][j - a[i].w];
else if (Value == LF[i][j]) LG[i][j] = (LG[i][j] + LG[i][j - a[i].w]) % P;
}
}
rep(i, mid + 1, r) {
rep(j, 0, m) {
RF[i][j] = RF[i - 1][j];
RG[i][j] = RG[i - 1][j];
}
reo(j, m, a[i].w) {
int Value = RF[i][j - a[i].w] + a[i].v;
if (Value > RF[i][j]) RF[i][j] = Value, RG[i][j] = RG[i][j - a[i].w];
else if (Value == RF[i][j]) RG[i][j] = (RG[i][j] + RG[i][j - a[i].w]) % P;
}
}
rep(i, mid + 1, r) {
Max[i][0] = RF[i][0], MxSumG[i][0] = RG[i][0];
rep(j, 1, m) {
Max[i][j] = Max[i][j - 1], MxSumG[i][j] = MxSumG[i][j - 1];
if (RF[i][j] > Max[i][j]) Max[i][j] = RF[i][j], MxSumG[i][j] = RG[i][j];
else if (RF[i][j] == Max[i][j]) MxSumG[i][j] = (MxSumG[i][j] + RG[i][j]) % P;
}
}
vector<int> Left, Right;
for (int id : vec) {
auto & now = qq[id];
if (now.l <= mid && mid < now.r) {
int F = 0, G = 0;
rep(i, 0, now.m) {
int Value = LF[now.l][i] + Max[now.r][now.m - i];
int nowG = 1ll * LG[now.l][i] * MxSumG[now.r][now.m - i] % P;
if (Value > F) F = Value, G = nowG;
else if (Value == F) G = (G + nowG) % P;
}
ans[now.id] = make_pair(F, G);
} else if (now.r <= mid) {
Left.push_back(id);
} else if (mid < now.l) {
Right.push_back(id);
} else {
assert(0);
}
}
Solve(l, mid, Left), Solve(mid + 1, r, Right);
}
int main() {
freopen("knapsack.in", "r", stdin), freopen("knapsack.out", "w", stdout);
ios::sync_with_stdio(false), cin.tie(nullptr);
cin >> n;
rep(i, 1, n) {
cin >> a[i].v >> a[i].w;
}
cin >> q;
rep(i, 1, q) {
cin >> qq[i].l >> qq[i].r >> qq[i].m, qq[i].id = i;
m = max(m, qq[i].m);
}
vector<int> vec;
rep(i, 1, q) vec.push_back(i);
Solve(1, n, vec);
rep(i, 1, q) {
int p = ans[i].first, q = ans[i].second;
if (!p) cout << "0 0\n";
else cout << p << ' ' << q << '\n';
}
return 0;
}