题解：AT_abc388_g [ABC388G] Simultaneous Kagamimochi 2

lhz2022 · 2025-01-12 22:30:08 · 题解

考虑二分。

我们设 b_i 代表最后一个可以放到 a_i 上面的麻糬的下标与 a_i 的差。

容易发现，b 数组可以 O(n) 计算。

再根据本场比赛 E 题，我们发现，操作的本质就是使找出最大的 k 使得对于任意的 0\leq i \leq k 都有 a_{l+i}\times 2\leq a_{r-k+i}。

换句话说，就是区间前 i 个和后 i 个一一队员满足题目中要求的 2 倍关系。

那么这种对应关系就可以转化为 l+\max_{i=r-k+1}^r b_i \leq r-k+1。

那么一个很显然的做法就是使用某种数据结构维护 b 的区间最大值。我们可以用 st 表维护，并二分计算 k 的值。

预处理时间复杂度：O(n \log n)，单次询问时间复杂度：O(\log n)，总复杂度 O((n+q) \log n)。

代码