回顾对于给定递增序列 $a_1\le a_2\le \cdots\le a_n$ 求答案的过程:
- 找到最小的 $i$ 使得对所有的 $j\le i$,$a_i\ge a_j-a_1-a_2-\cdots-a_{j-1}+k$。
- 注意如果 $i$ 满足条件,则 $i+1$ 也满足条件。
- 只有这些满足条件的 $i$ 才可能在吃掉 $1,2,\ldots,i-1$ 后继续吃掉 $i+1$;同时,如果无法继续吃掉 $i+1$,则 $i+1$ 一定可以依次吃掉 $1,2,\ldots,i$。
- 如果不存在满足条件的 $i$,根据上述性质,只有 $n$ 可能获胜。
- 令 $x=i$,枚举每个史莱姆 $j=i+1,\ldots,n$,如果当前 $x$ 能够吃掉 $j$($a_1+a_2+\cdots+a_{j-1}\ge a_j+k$),那么吃掉 $j$,否则 $1,2,\ldots,j-1$ 都不可能获胜,因此令 $x=j$。
- 能够获胜的史莱姆即为 $x,x+1,\ldots,n$。
考虑利用值域 $[2^j,2^{j+1})$ 分段的技巧优化上述过程。
对于第一步,只有每一段中的第一个数可能是 $a_j-a_1-a_2-\cdots-a_{j-1}+k$ 的前缀最大值,因此先判断每一段的最后一个数是否满足条件,如果满足,则二分出第一个满足条件的数。
如果找不到满足条件的 $i$,容易判断最后一个数是否能够获胜(如果能获胜,它一定是所在段中的唯一一个数)。
接下来我们从 $i$ 所在的段开始,枚举每一段,先判断能否吃掉这一段中的第一个数 $y_1$,如果可以,则可以吃掉这一段中的所有数(因为 $(2^j+k)+2^j=2^{j+1}+k$);否则,令 $x$ 为 $y_1$,注意此时不一定能吃掉所有数,因此还要判断是否能吃掉第二个数 $y_2$(如果存在),如果不能,则令 $x=y_2$,此时就一定可以吃掉这一段的所有数了。
注意最开始 $i$ 所在的段已经有一些数被吃掉了,但处理的方式完全类似于后面的段。
需要支持的操作是区间求值域段中的最小值、次小值、最大值,以及区间后继。每次询问需要 $O(\log W)$ 次 RMQ 和一次后继查询,因此可以做到 $O((n+q)(\log n+\log W))$ 的复杂度。