题解：CF2089D Conditional Operators

· · 题解

场上的复杂做法，没写出来。

根据泵引理，存在点数较少的自动机判断字符串的合法性。

所以将能判断能否缩成 0,1,00,01,10,11 的 6 个 DFA 建出来。构造方案使用启发式分裂，并用猫树判断一段子区间的合法性，递归下去做就好了，复杂度一只 log。