一个长度为 $ n $ 的大数，用 $ S_1S_2S_3 \ldots S_n $表示，其中 $ S_i $ 表示数的第 $ i $ 位，$ S_1 $ 是数的最高位，告诉你一些限制条件，每个条件表示为四个数 $( l_1, r_1, l_2, r_2 )$，即两个长度相同的区间，表示子串 $ S_{l_1}S_{l_1 + 1}S_{l_1 + 2} \ldots S_{r_1} $ 与 $ S_{l_2}S_{l_2 + 1}S_{l_2 + 2} \ldots S_{r_2} $ 完全相同。
比如 $ n = 6 $ 时，某限制条件 $ (l_1 = 1, r_1 = 3, l_2 = 4, r_2 = 6) $，那么 $ 123123 $,$ 351351 $ 均满足条件，但是 $ 12012 $,$ 131141 $ 不满足条件，前者数的长度不为 $ 6 $，后者第二位与第五位不同。问满足以上所有条件的数有多少个。
链接
题解
引用 zyqn 的话：
这题，出题人是怎么想到的QAQ，真心服 Orz
这是一道神题啊，建立 ST 表，每层维护一个并查集。
每个信息可以拆成两条长度为 $2$ 的幂次的区间相等的信息，等价于 ST 表里两对点的合并。
然后递归合并，一旦发现已经合并过了就退出。
时间复杂度 $O(n \text{ log } n \alpha(n))$
代码
1 | /* |
