「SCOI2016」「BZOJ-4569」萌萌哒-ST表+并查集

一个长度为 $ 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 $，后者第二位与第五位不同。问满足以上所有条件的数有多少个。

链接

BZOJ-4569

题解

引用 zyqn 的话：

这题，出题人是怎么想到的QAQ，真心服 Orz

这是一道神题啊，建立 ST 表，每层维护一个并查集。
每个信息可以拆成两条长度为 $2$ 的幂次的区间相等的信息，等价于 ST 表里两对点的合并。
然后递归合并，一旦发现已经合并过了就退出。
时间复杂度 $O(n \text{ log } n \alpha(n))$

代码

/*
 * created by xehoth on 01-04-2017
 */
#include <bits/stdc++.h>
int n, m, a, b, c, d, f[17][100010], v[100010], ans = 9, i, j;

inline int get(int i, int j) {
    return f[i][j] == j ? j : f[i][j] = get(i, f[i][j]);
}

inline void merge(int p, int x, int y) {
    if (get(p, x) == get(p, y)) return;
    f[p][f[p][x]] = f[p][y];
    if(!p) return;
    p--, merge(p, x, y), merge(p, x + (1 << p), y + (1 << p));
}

int main() {
    scanf("%d%d", &n, &m);
    if (n == 1) puts("10"), exit(0);
    for (i = 0; (1 << i) <= n; i++) 
        for(j = 1; j + (1 << i) - 1 <= n; j++)
            f[i][j] = j;
    while(m--) {
        scanf("%d%d%d%d", &a, &b, &c, &d), i = 31 - __builtin_clz(b - a + 1);
        merge(i, a, c), merge(i, b - (1 << i) + 1, d - (1 << i) + 1);
    }
    for (v[get(0, 1)] = 1, i = 2; i <= n; i++)
        if (!v[get(0,i)]) v[f[0][i]] = 1, ans = 10LL * ans % 1000000007;
    return printf("%d", ans), 0;
}