题解：P15499 [ICPC 2025 APC] Secret Lilies and Roses

luqyou · 2026-07-22 09:57:28 · 题解

考虑答案是什么。设共有 N_r 个 rose，那么我们对任意 i 均有 N_r-(i-l_i)=r_i，代入条件 l_i=r_i 可得 i=N_r。也就是说，我们只需要找出这个序列中 rose 的数量，这就是答案。

根据上述式子我们知道，答案 N_r=i-l_i+r_i。所以我们现在希望对于一个下标 i，通过若干个乘积的形式来凑出 r_i-l_i。观察移动下标 i \to i+1 时，l_ir_i 的变化：

• 若 i+1 为 lily，则 l_{i+1}r_{i+1}=(l_{i}+1)r_{i}，变化量为 r_i；

• 若 i+1 为 rose，则 l_{i+1}r_{i+1}=l_i(r_i-1)，变化量为 -l_i。

这启发我们去找到一对相邻的 rose-lily，记其中 rose 的下标为 x，那么 x+l_{x+1}r_{x+1}-l_{x-1}r_{x-1} 即为答案。问题转化为如何在 8 次询问内找出一个这样的下标。

不妨设 0 处为 rose，n+1 处为 lily，考虑进行二分。每次若二分到的位置为 rose 则向右递归，否则向左递归，这样能够保证要么左侧是一个 rose，要么右侧是一个 lily，最终走到的位置一定有 rose-lily。

注意特判 x=1 与 x=n 的 corner，这些都是平凡的。

询问次数为 \lceil \log_2n \rceil + 2，可以通过。