「SCOI 2016」萌萌哒

题目大意：

考虑一个暴力，将需要相等的点放到一个并查集里，设最后并查集的个数是 $k$，则答案为 $9 \times 10^{k-1}$，复杂度 $O(nm)$。

正解是建一棵并查集树，第 $j$ 层第 $i$ 个节点表示区间 $[i,i+2^j]$，如下为合并区间 $[1,4]$ 和 $[5,8]$ 的情况，虚线箭头为代码注释中的操作 $1$，实线箭头为操作 $2$，合并过程详见代码。

#include <cstdio>

const int N = 100005, P = 1e9+7;
int fa[20][N], a[N], cnt;

int read() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}
int pow(int a, int b) {
    int res = 1;
    for (; b; b >>= 1, a = 1LL * a * a % P)
        if (b & 1) res = 1LL * res * a % P;
    return res;
}
int find(int x, int y) {
    if (fa[x][y] != y) fa[x][y] = find(x, fa[x][y]);
    return fa[x][y];
}
void merge(int k, int x, int y) {
    int fx = find(k, x), fy = find(k, y);
    if (fx != fy) fa[k][fx] = fy;
}

int main() {
    int n = read(), m = read();
    for (int i = 0; 1 << i <= n; ++i)
        for (int j = 1; j + (1 << i) - 1 <= n; ++j)
            fa[i][j] = j;
    for (int i = 2; i <= n; ++i) a[i] = a[i>>1] + 1; //计算层数
    while (m--) { //操作1
        int l1 = read(), r1 = read(), l2 = read(), r2 = read();
        merge(a[r1-l1+1], l1, l2); //因为有可能r1-l1+1不是2的整数幂, 所以要合并两次
        merge(a[r1-l1+1], r1 - (1 << a[r1-l1+1]) + 1, r2 - (1 << a[r1-l1+1]) + 1);
    }
    for (int i = a[n]; i; --i) { //操作2
        for (int j = 1; j + (1 << i) - 1 <= n; ++j) {
            merge(i - 1, j, find(i, j));
            merge(i - 1, j + (1 << i - 1), find(i, j) + (1 << i - 1));
        }
    }
    for (int i = 1; i <= n; ++i) if (find(0, i) == i) ++cnt;
    printf("%lld\n", 9LL * pow(10, cnt - 1) % P);
    return 0;
}

时间复杂度 $O(n \log n)$