11.20 C 盲盒流水线

题解 ： 盲盒流水线

link
给定 \(n\) 个物品，每个物品有价值和质量，\(q\) 次询问，在 \([l , r]\) 中选质量不超过 \(m\) 的物品，每个物品至多选一次，并且要让价值最大
$ 1 \leq n \leq 20000$
$ 1 \leq m_i \leq 500$
$ 1 \leq q \leq 100000$
第一眼，这不是背包吗？
暴力：\(O(nmq)\) \(49pts\)
[code]const int N = 2e4 + 20, mod = 998244353;int n, v[N], w[N], q, g[N], f[N], p[N];signed main(){     ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);    cin >> n;    for(int i = 1; i > v >> w;    cin >> q;    for(int qwq = 1, l, r, m, cnt = 0; qwq > l >> r >> m;        g[0] = 1;        for(int i = l; i = w; --j){                if(f[j] < f[j - w] + v)f[j] = f[j - w] + v, g[j] = g[j - w] % mod ;                else if(f[j] == f[j - w] + v)f[j] = f[j - w] + v, (g[j] += g[j - w]) %= mod;               }        }        for(int i = 1; i > qwq;    B = n / (sqrt(qwq) + 1) + 1, cnt = n / B;    for(int i = 1; i  r_ >> m_;        if(bel[l_] == bel[r_]){            g[0] = 1;int as = 0, zz = 0;            for(int i = l_; i = w; --j){                    if(f[j] < f[j - w] + v)f[j] = f[j - w] + v, g[j] = g[j - w] % mod ;                    else if(f[j] == f[j - w] + v)f[j] = f[j - w] + v, (g[j] += g[j - w]) %= mod;                       zz = f[zz] < f[j] ? j : zz;                }            }            for(int i = 1; i  q.r >> q.m, q.id = i;    solve(1, n, 1, qwq);    for(int i = 1; i