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