幸运查询 题解

思路

一个区间只需维护四个量：字符 4 数量 $c_4$、字符 7 数量 $c_7$、最长 4...7 子序列长度 $d_{47}$，以及最长 7...4 子序列长度 $d_{74}$。

合并左右区间 $A,B$ 时，

另一方向同理。区间翻转会交换 $c_4,c_7$，并交换 $d_{47},d_{74}$，因此可用带懒标记的线段树维护。

做法

子任务 1 在每次 count 时枚举所有子序列，筛选不下降者，复杂度 $O(m2^n n)$。

子任务 2 直接执行区间翻转；每次 count 枚举 4 与 7 的分界位置并线性求最优，复杂度 $O(nm)$。

满分算法建立线段树。区间翻转时交换上述两对量并翻转懒标记；count 的答案就是根节点的 $d_{47}$。

正确性证明

任意跨越左右区间的不下降子序列，要么取左区间若干 4 后接右区间最优 4...7 子序列，要么取左区间最优 4...7 子序列后接右区间若干 7，合并式覆盖且只覆盖这两种可能。字符互换后，4...7 与 7...4 的角色完全交换，懒翻转保持四个量正确。由线段树归纳，根节点始终给出整个字符串的最长不下降子序列。

复杂度

建树 $O(n)$；每次 switch 为 $O(\log n)$，每次 count 为 $O(1)$；空间复杂度 $O(n)$。