3649.小跳蛙
2026-09-28
题解
发现 21 这样的排列会导致这个 1 被跳过,所以我们尽量让 2 两两配对,令 si 表示将第 i 个 2 和第 i+1 个 2 配对,第 i+2 个 2 和第 i+3 个 2 配对,以此类推。
现在对于询问的区间 [l,r],它对应 2 是第 p 个到第 q 个。
发现有偶数个 2 时可以两两配对或者中间一个任意,多余的 2 放在最后。
为奇数时,将多余的 2 放在最后,答案为 sp−sq+(r−posq)。
为偶数时,两两配对答案为 sp−sq+1;另一种是跳过第 i 个 2(p≤i≤q 且 i 前面能成功配对,即 i 与 p 同奇偶), 让 q 到最后,答案为 sp−si+si+1−sq+(r−posq),进而转换为 si+1−si 的分奇偶 RMQ 问题。
