P6240
既然在这题碰到了这个算法，那么就以这道题引入吧
这个东西是个传统的背包问题，然后加上了一个区间的限制。
注意数据范围，发现背包容量很小，这启示我们可以暴力把 \(dp\) 数组存下来。我们合并两个背包的复杂度是 \(40000\)，线段树不行，\(st\) 表预处理寄了。
这题的背包是 \(max\) 背包，所以比较难撤销贡献，
考虑分块，因为合并背包复杂度很高我们考虑维护维护块的前缀和，那么查询就是 \(len*200\)，没有修改，那么我们的预处理复杂度是 \(\frac{n}{len}*n*200\)
最优复杂度是 \(n\sqrt{n}*200\) 肯定过不了。
抛弃这些东西，我们离线搞一下。可不可以使用线段树分治？不可以吧。猫树，好吧，这是我不会的东西
猫树（分治树）
上面我们提到了 \(st\) 表，这个东西能维护重复贡献的东西，但是对于这题，不仅贡献不能重复，而且背包合并时间复杂度炸掉了。
我们想要这种效果，也就是我们能对于每个区间都能找到两个已经维护好的区间拼起来。
利用线段树的结构，也就是那个 \(p<<1,p<<1|1\) 的那种线段树。我们对于每段区间 \([l,r]\) 都维护 \([i,mid]\) 和 \([mid,i]\) 的答案。对于区间 \(l,r\)，我们发现它的 \(lca\) 就是它们的 \(lcp\)（不用末尾的 \(0\)），根据线段树的结构容易理解。
建树 \(O(n\log n)\)，查询 \(O(1)\)
对于上面这题，我们的建树 \(O(n\log n*200)\)，但是我们貌似不能直接把这个存下来，这样询问也是 \(200^{2}\)，时间和空间都爆了。
哥们的 \(dp\) 方程怎么这么写的。这个问题很久了吧。我的 \(dp\) 方程基本都是选的物品容量为 \(i\) 的最大值，也就是这个东西很严格，考虑改变转移状态，也就是物品容量 \(<=i\) 的时候的最大值，容易理解正确性那么 \(dp\) 初始值也就不用赋极小值，直接全部都是 \(0\) 就行了。那么我们其实在那个区间 \(O(1)\) 合并的时候，我们不用花 \(40000\) 的时间合并背包。我们直接 \(\sum_{i=0}^{s} dpl[i]+dpr[s-i]\) 即可。那么我们离线挂询问是不是就可以了。
所以我们合并背包是不是可以用fft优化yes！
离线的空间复杂度是 \(O(nt)\)，在线是 \(O(nt\log n)\) 然后就做完了