jiangly的博客

博客

【PR #2】史莱姆 更优秀的解法

2022-04-09 18:52:35 By jiangly

回顾对于给定递增序列 a1a2an 求答案的过程:

  • 找到最小的 i 使得对所有的 jiaiaja1a2aj1+k
    • 注意如果 i 满足条件,则 i+1 也满足条件。
    • 只有这些满足条件的 i 才可能在吃掉 1,2,,i1 后继续吃掉 i+1;同时,如果无法继续吃掉 i+1,则 i+1 一定可以依次吃掉 1,2,,i
    • 如果不存在满足条件的 i,根据上述性质,只有 n 可能获胜。
  • x=i,枚举每个史莱姆 j=i+1,,n,如果当前 x 能够吃掉 ja1+a2++aj1aj+k),那么吃掉 j,否则 1,2,,j1 都不可能获胜,因此令 x=j
  • 能够获胜的史莱姆即为 x,x+1,,n

考虑利用值域 [2j,2j+1) 分段的技巧优化上述过程。

对于第一步,只有每一段中的第一个数可能是 aja1a2aj1+k 的前缀最大值,因此先判断每一段的最后一个数是否满足条件,如果满足,则二分出第一个满足条件的数。

如果找不到满足条件的 i,容易判断最后一个数是否能够获胜(如果能获胜,它一定是所在段中的唯一一个数)。

接下来我们从 i 所在的段开始,枚举每一段,先判断能否吃掉这一段中的第一个数 y1,如果可以,则可以吃掉这一段中的所有数(因为 (2j+k)+2j=2j+1+k);否则,令 xy1,注意此时不一定能吃掉所有数,因此还要判断是否能吃掉第二个数 y2(如果存在),如果不能,则令 x=y2,此时就一定可以吃掉这一段的所有数了。

注意最开始 i 所在的段已经有一些数被吃掉了,但处理的方式完全类似于后面的段。

需要支持的操作是区间求值域段中的最小值、次小值、最大值,以及区间后继。每次询问需要 O(logW) 次 RMQ 和一次后继查询,因此可以做到 O((n+q)(logn+logW)) 的复杂度。

评论

[0]
orz
  • 2023-10-15 15:33:53
  • Reply

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。