GDKOI 选做

不休陀螺

题目描述

这里

思路点拨

考虑一个区间在什么情况下是“陀螺无限”的。一个最为简单的条件就是 \(\sum_{i=l}^r b_i-a_i \geq 0\) 。因为如果不满足这个，\(E\) 就会一直减少，就会在某一个时刻停下来。

当然，还有别的条件，比如说在中途某一个时刻 \(E+\sum_{i=l}^{mid}b_i-a_i <a_{mid+1}\) ,然后就无法继续打下去了。这个时候我们对于 \(b_i-a_i\) 是否非负展开两类讨论。

• \(b_i-a_i \geq 0\)

我们可以在某一个排列中，让 \(i\) 之前一直安排 \(b_j-a_j<0\) 的元素，这个时候 \(E\) 就会达到最小，进而可能发生无法继续下去。令 \(sum=\sum_{i=l}^r (b_i-a_i)[b_i-a_i<0]\) ，则 $\forall i \in [l,r] $ ，若 \(b_i-a_i \geq 0\) ，则需要满足 \(E \geq a_i-sum\) 。

• \(b_i-a_i <0\)

同理，我们希望在 \(i\) 之前一直安排 \(b_j-a_j<0\) 的元素，只不过不可以安排它自己了。需要满足：

也就是 \(E \geq b_i-sum\) 。

现在我们以及知道了一个区间在什么情况下是合法的了。但是需要计数需要我们注意到一些性质。假设存在 \(L<l \leqslant r<R\) ，如果 \([L,R]\) 满足陀螺不休，那么 \([l,r]\) 也会满足；如果 \([l,r]\) 不满足陀螺不休，那么 \([L,R]\) 也不满足。证明是简单的。

下文暂时不考虑 \(\sum b_i-a_i \geq 0\) 的限制。
我们考虑对于某一个固定的左端点 \(l\) ，找到一个右端点 \(r_l\) 满足 \([l,r_l]\) 是陀螺不休的并且 \(r_l\) 尽量大。我们知道上述性质，则在 \(l\) 不断变大的时候 \(r_l\) 不会变小。这样子我们可以双指针。

问题转化为现在维护了一个集合，如何加入一个元素然后判断是否合法。我们考虑维护一个集合 \(S\) ，并且维护集合的 \(sum\) （定义和之前是一样的），每一次加入集合的时候就更新 \(sum\) 。并且根据 \(b_i-a_i\) 是否非负决定加入 \(a_i\) 还是 \(b_i\) 到集合 \(S\) 里面。这个区间合法就是 \(S\) 的最大值减去 \(sum\) 的值是否小于等于 \(E\) 。集合可以使用 STL_set。

现在如果我们以及求出了 \(l,r_l\) 还需要满足 \(\sum b_i-a_i \geq 0\) 的约束。记前缀和 \(sum_i=\sum_{1 \leqslant j \leqslant i}b_j-a_j\) ，也就是对于区间 \([l,r_l]\) 存在多少个 \(sum_i \geq sum_{l-1}\) 。这个可以使用线段树之类的维护，因为值域太大，但是动态开点线段树开不下这么大空间所以使用了平衡树实现。

时间复杂度 \(O(n \log n)\) 。

实现细节：本题时间比较紧，无旋treap过不了。建议使用更加快速的平衡如例如 \(\text{WBLT}\) 实现。