SCOI 2016 萌萌哒

solution

有点线段树的味道，但是并不是用线段树来做，而是用到另外一个区间修改和查询的利器——ST表

我们可以将一个点拆成\(logN\)个点，分别代表从点\(i\)开始，长度为\(2^k\)的子串 那么当我们处理两个区间相等的关系时，对区间做二进制拆分，拆成\(log\)个区间，分别并起来即可

我们从最长的区间开始逐个枚举，每次查找他和他的父亲，然后把它和父亲都劈成两半，前一半和前一半连边，后一半和后一半连边即可，这样相当于把较长区间并查集拆成两个一半的并查集

#include <cmath>

#include <cstdio>

using namespace std;

int n, m, fa[100005][18], ans;

int find(int x, int k) { return fa[x][k] == x ? x : fa[x][k] = find(fa[x][k], k); }

void join(int x, int y, int k) { if ((x = find(x, k)) != (y = find(y, k))) fa[x][k] = y; }

int main() {

    scanf("%d %d", &n, &m);

    int maxk = floor(log2(n));

    for (int i = 1; i <= n; ++i)

        for (int k = 0; k <= maxk; ++k) fa[i][k] = i;

    for (int i = 1, l1, r1, l2, r2; i <= m; ++i) {

        scanf("%d %d %d %d", &l1, &r1, &l2, &r2);

        for (int k = maxk; ~k; --k)

            if (l1 + (1 << k) - 1 <= r1)

                join(l1, l2, k), l1 += 1 << k, l2 += 1 << k;

    }

    for (int k = maxk; k; --k)

        for (int i = 1; i + (1 << k) - 1 <= n; ++i) {

            int pos = find(i, k);

            join(i, pos, k - 1);

            join(i + (1 << k - 1), pos + (1 << k - 1), k - 1);

        }

    for (int i = 1; i <= n; ++i)

        if (fa[i][0] == i) ans = !ans ? 9 : ans * 10ll % 1000000007;

    printf("%d\n", ans);

    return 0;

}