题解：CF2048I2 Kevin and Puzzle (Hard Version)

Little09 · 2024-12-25 10:51:58 · 题解

根据简单版本，可以发现大部分情况解的个数并不多，因为对于 LR，LL 和 RR，对于里面的部分填完后，外层只有唯一的填法。因此如果没有一层是 RL，那么答案必然是 1。

接下来考虑有 RL 的情况，不妨假设 RL 是最外部的两个字符。

可以证明的是：这个 RL 中 R 位置和 L 位置填的数是相同的。具体证明在此省略，读者自证不难。

不妨设这个相同的值为 m。接下来，枚举最右侧填 m 的 R 位置 x，和最左侧填 m 的 L 位置 y。讨论一下 x,y 的关系：

• 若 x>y，可以发现 x 右边的 L 都需要填 m，而 x 右边的 R 只有唯一的填法。对 y 同理。对这种情况计算，我们可以直接枚举 m，然后就可以确定唯一的 x,y 位置，并检查是否满足 x>y。

• 若 x<y，此时 x 左边的 R 都只能填 m，左边的 L 是唯一的填法。对 y 的右侧同理。再考虑 (x,y) 中间的部分，显然 m 必然没有在中间出现，因此我们可以删除 x 及其左边的 R，y 及其右边的 L（也就是删除所有值为 m 的位置），称得到的新序列为剩余序列。删除这些字符后，我们解决剩余序列，再对得到的数全部 +1，然后加入所有数为 m 的位置即可。

  以下为一个初始序列的例子，其中红色的字符为 x 和 y，省略的部分是 (x,y) 中间的部分。

  \textbf{R L L R R L L }\color{red}\textbf{R}\color{black}\textbf{ ... }\color{red}\textbf{L}\color{black}\textbf{ L R R L}\\\textbf{ m 1 2 m m 3 4 m ... m m 2 1 m}

  以下为上述对应的剩余序列，* 对应原序列中 x,y 的位置。

  \textbf{L L L L }\color{red}\textbf{*}\color{black}\textbf{ ... }\color{red}\textbf{*}\color{black}\textbf{ R R}\\\textbf{ 1\ 2\ 3\ 4 * ... * 2 \ 1}

  在填完剩余序列后，需要分析加入所有数为 m 的位置的条件：我们将剩余序列分为“左”、“中”、“右”三个部分，以 x,y 的位置为分界线，其中左部分只有 L，右部分只有 R。则要求是，记“左中”部分的颜色总数为 c_1，“中右”部分的颜色总数为 c_2，那么需要满足 m=c_1+1=c_2+1。同时还要求 m 不在剩余序列中出现，该限制等价于对于“左中”部分和“中右”部分，都满足 d=1。可以推出等价于剩余序列满足 d=1。对于条件 c_1=c_2，容易发现其等价于：记 z 为左部分和右部分的个数较大值，则剩余序列最左边 z 个字符必须全为 L，最右边 z 个字符必须全为 R。

  这部分的最终得出的充要条件是：记 x 左边有 a 个 L，y 右边有 b 个 R，不妨假设 a\ge b，取出 (x,y) 中间的字符串（不包含 x,y），需要满足末尾有连续 a-b 个 R，且去这 a-b 个 R 后，得到的字符串满足 d=1，即每次取出首尾字符时不存在 RL 的情况。由于 d=1，因此若剩余序列满足该条件，则存在恰好一种填法。

最后仅需要对上述情况分别计数即可。x>y 的情况容易 O(n) 统计，对于 x<y 的情况，不妨 a\ge b，可以枚举 y，计算出 y 前面连续的极长 R 的个数 cnt，那么对 a 的限制变成了 b\le a\le b+cnt。

• 当 cnt=0 时，a 的值固定，但对应的 x 可以在某一个 R 连续段中任意选择一个位置。我们发现由于 cnt=0，也就是 y 前面一个位置填的是 L，那么 x 后面一个位置就不能填 R，所以 x 只能取这个 R 连续段中的最后一个 R。
• 当 cnt>0 时，只需要枚举 x 的值。容易发现每个 x 只会被计算至多 2 次。

通过上述观察，我们总共只需要枚举 O(n) 组 x,y 并判断其是否会对答案增加 1。也就是说，答案是 O(n) 级别的。

最后的问题是：每次给定一组区间 [l,r]，问这个字符串每次取出首尾字符时，是否存在 RL 的情况。

一种简单的解决方法是，使用 bitset 维护，例如从小到大扫描 r，以 bitset 维护对于每个 l+r，是否存在 RL 的情况。该做法的时间复杂度为 O(\dfrac {n^2}{\omega})，可以通过本题。

如果使用分块卷积，可以做到更优的复杂度。事实上，如果继续深挖性质，可以做到 O(n\log ^2n) 的时间复杂度（需要使用卷积），如果你对此感兴趣可以自行研究。