P4587 [FJOI2016] 神秘数
赛时想的做法（不知道能否通过）：
考虑给出集合怎么求它的神秘数。
将所有元素排序，模拟从小往大求子集的和的过程。
设排序完后为 \(a_1,a_2,\dots,a_n\)。
设当前考虑完前 \(k\) 个，\(\sum_{i=1}^k a_i=S\)，并且 \([0,S]\) 都能取到（不然已经不合法在前面会被判掉）。
若 \(a_{k+1}\le S+1\)，则 \(S+t-a_{k+1}\in [0,S](t=1\sim a_{k+1})\)，也就是说一定可以在前面找出子集使得和为 \(S+t-a_{k+1}\)，再加入 \(a_{k+1}\) 使得 \([0,S+a_{k+1}]\) 都能取到，将 \(k\gets k+1\) 继续判断。
否则 \(S+1\) 一定取不到，结果为 \(S+1\)。
考虑莫队，对于一个集合 \(a\)，和 \(k\) 满足 \(a_{k+1}>S=\sum_{i=1}^k a_i+1\)，加入了一个值 \(x\)：
1.若 \(x\ge a_{k+1}\) 显然对答案没有影响，放置在后面。
2.若 \(x\le a_k\)，则 \(x\) 可以被选中，让 \(S\gets S+x\) 再往后判断。
3.若 \(a_k<x<a_{k+1}\)，判断是否有 \(x\le S\)，若满足则将 \(S\gets S+x\)，并继续考虑 \(k+1\)，否则将 \(x\) 放在 \(k+1\) 前面。
分析一下时间复杂度，1 操作可以用优先队列 \(\mathcal O(\log n)\) 维护，2,3 的均摊时间复杂度是操作次数 \(\times\mathcal O(\log n)\)，加上回滚莫队总时间复杂度为 \(\mathcal O(n\sqrt{m}\log n)\)。
实际上求神秘数的结论是正确的，但没有必要用这种方式维护。
事实上，若求神秘数时当前和为 \(S\)，相当于一次可以取所有值在 \([1,S]\) 的元素，\(S\gets \sum_{i=l}^r a_i[a_i\in[1,S]]+1\)。
对于 \(\sum_{i=l}^r a_i[a_i\in[1,S]]\) 可以用主席树 \(\mathcal O(\log n)\) 维护，而对于 \(S\) 的变化每次暴力进行上面的操作，操作次数是 \(\mathcal O(\log n)\)。