题目
区间 (01) 背包
(1 le l_i le r_i le n le 20000,1 le q le 100000,1 le m_i le 500, 1 le w_i le 500, 1 le v_i le 10^6)
分析
显然,我们考虑区间背包的合并
于是可以考虑分治策略
我们每次处理跨区间的询问
那么可以以 (mid) 为起点,往左做一遍后缀背包(不一定装满),往右做一遍前缀背包(一定装满)
一个在本区间且跨 (mid) 的询问就可以用这些拼起来,统计答案即可
不在本区间的分治处理即可
上面限制了背包装不装满是为了不重复的统计
于是时间复杂度就是 (O(nmlog n + qm))
(Code)
#include<cstdio>
#include<vector>
#define ls (k << 1)
#define rs (ls | 1)
using namespace std;
const int N = 2e4 + 5, M = 505, Q = 1e5 + 5;
const int INF = 0x3f3f3f3f, P = 998244353;
int n, q, Mx, v[N], w[N], f[N][M], g[N][M];
struct node{int l, r, m;}a[Q];
struct answer{int val, g;}ans[Q];
vector<int> st[Q << 2];
void solve(int k, int L, int R)
{
if (!st[k].size()) return;
int mid = (L + R) >> 1;
f[mid][0] = 0, g[mid][0] = 1;
for(register int i = mid; i <= R; i++)
{
g[i][0] = 1;
for(register int j = 1; j <= Mx; j++) f[i][j] = -INF, g[i][j] = 0;
}
for(register int i = mid + 1; i <= R; i++)
{
for(register int j = 0; j <= Mx; j++) f[i][j] = f[i - 1][j], g[i][j] = g[i - 1][j];
for(register int j = w[i]; j <= Mx; j++)
{
int val = f[i - 1][j - w[i]] + v[i];
if (val > f[i][j]) f[i][j] = val, g[i][j] = g[i - 1][j - w[i]];
else if (val == f[i][j]) g[i][j] = (g[i][j] + g[i - 1][j - w[i]]) % P;
}
}
for(register int i = mid; i >= L; i--)
for(register int j = 0; j <= Mx; j++) f[i][j] = 0, g[i][j] = 1;
for(register int i = w[mid]; i <= Mx; i++) f[mid][i] = v[mid], g[mid][i] = 1;
for(register int i = mid - 1; i >= L; i--)
{
for(register int j = 0; j <= Mx; j++) f[i][j] = f[i + 1][j], g[i][j] = g[i + 1][j];
for(register int j = w[i]; j <= Mx; j++)
{
int val = f[i + 1][j - w[i]] + v[i];
if (val > f[i][j]) f[i][j] = val, g[i][j] = g[i + 1][j - w[i]];
else if (val == f[i][j]) g[i][j] = (g[i][j] + g[i + 1][j - w[i]]) % P;
}
}
for(register int i = 0; i < st[k].size(); i++)
{
int now = st[k][i], l = a[now].l, r = a[now].r, m = a[now].m;
if (l == mid && r == mid) ans[now].val = ((m >= w[mid]) ? (v[mid]) : 0), ans[now].g = 1;
else if (l > mid) st[rs].push_back(now);
else if (r <= mid) st[ls].push_back(now);
else{
for(register int j = 0; j <= m; j++)
{
int val = f[r][j] + f[l][m - j];
if (val > ans[now].val) ans[now].val = val, ans[now].g = (long long)g[r][j] * g[l][m - j] % P;
else if (val == ans[now].val) ans[now].g = (ans[now].g + (long long)g[r][j] * g[l][m - j]) % P;
}
}
}
if (L == R) return;
solve(ls, L, mid), solve(rs, mid + 1, R);
}
int main()
{
freopen("knapsack.in", "r", stdin);
freopen("knapsack.out", "w", stdout);
scanf("%d", &n);
for(register int i = 1; i <= n; i++) scanf("%d%d", &v[i], &w[i]);
scanf("%d", &q);
for(register int i = 1; i <= q; i++)
scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].m), Mx = max(Mx, a[i].m), st[1].push_back(i);
solve(1, 1, n);
for(register int i = 1; i <= q; i++)
{
if (ans[i].val == 0) printf("0 0
");
else printf("%d %d
", ans[i].val, ans[i].g);
}
}