Q u e s t i o n Question Question
一个长度为 n n n 的大数，用 S 1 S 2 S 3 ⋯ S n S_1S_2S_3 \cdots S_n S1S2S3⋯Sn表示，其中 S i S_i Si 表示数的第 i i i 位, S 1 S_1 S1 是数的最高位。告诉你一些限制条件，每个条件表示为四个数， l 1 , r 1 , l 2 , r 2 l_1,r_1,l_2,r_2 l1,r1,l2,r2，即两个长度相同的区间，表示子串 S l 1 S l 1 + 1 S l 1 + 2 ⋯ S r 1 S_{l_1}S_{l_1+1}S_{l_1+2} \cdots S_{r_1} Sl1Sl1+1Sl1+2⋯Sr1与 S l 2 S l 2 + 1 S l 2 + 2 ⋯ S r 2 S_{l_2}S_{l_2+1}S_{l_2+2} \cdots S_{r_2} Sl2Sl2+1Sl2+2⋯Sr2完全相同。
比如 n = 6 n=6 n=6 时，某限制条件 l 1 = 1 , r 1 = 3 , l 2 = 4 , r 2 = 6 l_1=1,r_1=3,l_2=4,r_2=6 l1=1,r1=3,l2=4,r2=6 ，那么 123123 123123 123123， 351351 351351 351351 均满足条件，但是 12012 12012 12012， 131141 131141 131141 不满足条件，前者数的长度不为 6 6 6 ，后者第二位与第五位不同。问满足以上所有条件的数有多少个。
S o l u t i o n Solution Solution
倍增骚操作了解一下
最直观的方法便是 N 2 N^2 N2并查集 它主要慢在了一个一个操作合并 于是我们考虑整个区间合并： 还记得 S T ST ST表是怎样询问的吗？ l e n = r − l + 1 len = r - l + 1 len=r−l+1 拆成 [ l , l + 1 < < l o g l e n ] [l,l + 1<<loglen] [l,l+1<<loglen]和 [ r − 1 < < l o g l e n + 1 , r ] [r -1<<loglen+1,r] [r−1<<loglen+1,r] 于是，我们可以开 l o g M A X N logMAXN logMAXN个并查集 F a [ i ] [ j ] Fa[i][j] Fa[i][j]表示左端点为 j j j,长度为 2 i 2^i 2i的区间 读入完后就从大到小，将大区间拆成两个 最后统计 F a [ 0 ] Fa[0] Fa[0]中集合的个数就可以辣！
给出拆分区间的代码：
for (int i = log[N];i > 0;i--) { for (int j = 1;j <= N - (1 << i) + 1;j++) { Union(j,Find(j,i),i - 1); Union(j + (1 << (i - 1)),Find(j,i) + (1 << (i - 1)),i - 1); }