科技改变生活

qczrz6v4nhp6u · 2025-06-20 22:35:49 · 题解

一个思维量小很多的做法。

Solution

哇又是神秘操作判定合不合法，考虑类似 P12294 搞一个 DFA 出来判定。

但是会遇到问题：字符集的大小实在太大。尝试把字符集缩小到常数级。

注意到对于一组询问 (x,y)，只有 a_i 与 x 的大小关系和 b_i 与 y 的大小关系有用。令 {\rm sgn}(x)=[x>0]-[x<0]（即 x>0 时为 1，x=0 时为 0，x<0 时为 -1），则我们可以将 a_i\gets {\rm sgn}(a_i-x),b_i\gets {\rm sgn}(b_i-y)，最后查询能否合出 (0,0) 即可。

那么现在的字符集已经小到足够搞一个 DFA 出来了。沿用 P12294 的方法：设阈值 X,Z，枚举长度 \le X 的串 x,y，若对于所有长度 \le Z 的串 z 都有 f(x+z)=f(y+z)（f(s) 表示串 s 能否合出 (0,0)），则认为 x 和 y 等价。每个等价类中任意取出一个长度最小的字符串，按照转移关系即可建出 DFA。经过试验，本题中取 X=4,Z=3 即可造出正确的 DFA，此时 DFA 的点数为 24。

把这个 DFA 表出来，每次询问都在自动机上走即可获得一个 O(nq) 的做法，可以获得 71 分。

然后考虑优化。直接套一个 D2T2 做法应该可以做到 O((n+q)\sqrt{n|S|})（其中 S 为 DFA 的状态集合），然而太不优美了。尝试找一些 DFA 的性质。