【3.31】

思路：虚拟物品的思路。可以把 $l\in [1,k],r\in [k,n]$ 的区间 $(l,r)$ 看作一个虚拟物品，体积和价值为区间的体积和与价值和。这样做完全背包就是 $O(m^3)$ 的。用贪心去一下重的话是 $O(n^2)$ 的。

AC代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=68493724

思路：还是 DP 。

1. 考虑枚举分界点进行如上题的 DP，时间复杂度 $O(n\times m^3)$ 。
2. 考虑枚举虚拟物品，共有 $n^2$ 个，每个物品 $(l,r)$ 都对该区间内的所有分界点作为物品。如果我们从小到大枚举 $l$ ，从大到小枚举 $r$ ，可以将 $(l,r\in l\sim n)$ 内的所有物品一次统计到 $(l,r)$ 中。$r$ 枚举完之后，$k=l$ DP 完成。

三个知识点：支持 O1 反转的双端队列，整体打lazy标记，时间戳在lazy上的应用。

一、

自己写了个

struct ReversedDeque {int h, t, isrev, data[N];int _next(int i) { return i + 1 == N ? 0 : i + 1; }int _prev(int i) { return i == 0 ? N - 1 : i - 1; }int size() { return h <= t ? t - h : t - h + N; }void pop_back() { t = _prev(t); }void pop_front() { h = _next(h); }void push_back(int x) { data[t] = x; t = _next(t); }void push_front(int x) { h = _prev(h); data[h] = x; }int& front() { return data[h]; }int& back() { return data[_prev(t)]; }int& at(int i) { i = h + i; if(i >= N) i -= N; return data[i]; }void reverse() { isrev ^= 1; }void r_pop_back() { isrev ? pop_front() : pop_back(); }void r_pop_front() { isrev ? pop_back() : pop_front(); }void r_push_back(int x) { isrev ? push_front(x) : push_back(x); }void r_push_front(int x) { isrev ? push_back(x) : push_front(x); }int& r_front() { return isrev ? back() : front(); }int& r_back() { return isrev ? front() : back(); }int& r_at(int i) { return isrev ? at(size() - 1 - i) : at(i); }
};

二、

该题涉及到的lazy标记是 1. 整体乘 2. 整体加

当塞入一个数字时，队列中其他数字都有lazy $A\times item+B$ ，而新数字没有。此时可以逆向打lazy，即 $\frac{item-B}{A}$ ，这样新数字的lazy就与整体的一致了。

三、不会，省略。

知识点：分层 BFS，开两个队列。

AC代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=68515129