loj6515 贪玩蓝月 题解
题意：你需要维护一个双端队列。有5种操作，共进行\(q\)次：
- 给定\(v,w\)，在队首加入一个物品，其体积为\(v\)，权值为\(w\)；
- 给定\(v,w\)，在队尾加入一个物品，其体积为\(v\)，权值为\(w\)；
- 删除队首的物品。
- 删除队尾的物品。
- 给定\(l,r\)，从队列中选取若干物品，在其体积之和对\(p\)（\(p\)为定值）取模后在\([l,r]\)中的情况下，最大化物品的权值和。如果没有合法方案，输出\(-1\)。
\(q\leq 50000,p\leq 500,0\leq w,v<10^9\)。
难度：省选 NOI-
算法一（10分）
对于询问，直接暴力枚举每个书选还是不选，按题意求解最大值即可。
时间复杂度：\(O(q2^q)\)
算法二（20分）
对于每个询问，实际上是一个01背包问题。直接套用01背包的做法即可。
注意因为有取模，所以背包容量\(v\)是一个“环”，如果要压掉一维需要考虑一些细节。
时间复杂度：\(O(q^2Mod)\)
算法三（5分，测试点12）
01背包模板题。
时间复杂度：\(O(qMod)\)
算法四（15分，测试点13-15）
特殊性质是只在一端加入和删除。
本题最大的痛点之一，就是如何处理01背包的撤销。那如果换种说法呢，把撤销叫为“回到上个版本”，是不是感觉清晰多了！
我们可以稍稍参考可持久化的思想，将每次修改完后的dp数据都保存一份。那么IG（加入）就是新开了一个长为Mod的dp数组，DG（删除）就是回到了之前的某一次修改完成后的状态，这个只需要记录下每个节点的father，即栈顶撤销后回到的状态编号即可。
时间复杂度：\(O(qMod)\)
算法五（100分）
观察测试点17、18——这部分测试点的特点在于其队列的特性——每本书加入、删除的时间点都是一段连续的区间，且所有书的加入、删除时间是单调递增的。转念一想，不只是这两个测试点，对于所有的数据，每本书的存在时间都是一段连续的区间，而在做01背包时，我们并不关心这本书在书架的哪个位置，只关心它的\(p\)和\(v\)。
对于这种每个物品的存在时间是一段连续区间的问题，我们会想到线段树分治。我们把每个物品的存在时间求出，在线段树上做区间修改，把询问存到线段树的叶子结点，最后遍历整颗线段树，在每个节点上都开一个长为Mod的数组，做01背包，这样总的空间复杂度为\(O(qMod)\)。通过这种方式，我们巧妙规避了删除的问题，可以通过本题。
时间复杂度：\(O(qModlogq)\)
算法六（10分，测试点15，16）
考虑有没有在线做法。本题如需在线，另一个痛点是如何处理两端的同时增删。
既然合起来不好做，能否干脆将双端队列分成两个栈来做呢？
观察测试点15,16，特殊性质为\(l=r\)。也就是说，如果选取了左边的一些书，它们的特征值和对\(Mod\)取模后为\(k_左\)，那么\(k_右\)是个定值。因此，只需要枚举一边的\(k\)，就能得到一个确定的值，单次询问的时间复杂度为\(O(Mod)\)，是ok的。
但这样又衍生出一个问题——如果一边被删光了，又要继续删，那会对另一边造成影响。但是右边又没法直接从栈底删，这该怎么办？
可以直接把另一边匀一半吗？这需要我们对整个dp数据进行重构，这个操作的时间复杂度是\(O(cnt\times Mod)\)的（\(cnt\)为当前书架上书的本数），我们可以接受吗？
答案是可以的。这里需要进行一些势能分析——
我们考虑一个变量\(\Delta=|cnt_左-cnt_右|\)，即两边书本个数差的绝对值。当增/删一本书时，\(\Delta\)会变化1，这样的时间复杂度是\(O(Mod)\)的；而当某一边的\(cnt\)归零后，我们要重构整个dp数组，使得新的\(cnt_左=cnt_右\)，这个操作花费的时间复杂度为\(O(cnt\times Mod=\Delta \times Mod)\)，之后\(\Delta\)会归零。
由此我们发现，这个做法的时间复杂度是均摊\(O(qMod)\)的，可以接受。
算法七（100分）
现在，只剩最后一个问题了——对于\(k_左\)，\(k_右\)可取的值是\(O(Mod)\)的，如果暴力枚举，那单次询问的时间复杂度将来到\(O(Mod^2)\)，不能接受。
手摸一下，观察一下，可以发现，对于\(k_左\),可行的\(k_右\)是一段连续区间（如果将\([0,Mod-1]\)看成一个环形区间）。进一步观察，发现当\(k_左\)增大时，可行的\(k_右\)区间是一个固定长度的滑动窗口，使用单调队列即可均摊\(O(Mod)\)地求出对于所有的\(k_左\),最大的\(k_右\)。
时间复杂度：\(O(qMod)\)，如果使用带log的数据结构维护区间max的话就是\(O(qModlogMod)\)。