BZOJ 4569 萌萌哒

题意：

https://www.lydsy.com/JudgeOnline/problem.php?id=4569

Sol：

首先考虑暴力，也就是每个限制按位合并并查集，复杂度\(nm\)。

这样的话就要减少无用的合并次数(即对于一对\((i,j)\)合并了很多次的情况)。

考虑像st表一样建出\(\log\)层的并查集，对于每个限制我们在不同的层开始合并

并且因为st表区间长度取log前后合并一定有重复的性质，这些只会有重复合并但是不会有多合并。

虽然仍然有重复合并，但是重复合并最多log次， 因此复杂度是对的。

注意从上一层过来的时候\(i\)要和上一层的\(i\)先合并一下，并且要开ll

#include <cstdio>
#include <iostream>
#include <cstring>
const int N = 2e5+7;
typedef long long LL;
#define R register
#define p 1000000007
int bin[N];
struct SET {
    int fa[N], siz[N];
    void init(int n) {
        for (R int i = 1; i <= n; i++)
            fa[i] = i, siz[i] = 1;
    }
    int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    inline int Union(int x, int y) {
        int a = find(x), b = find(y);
        if (a == b) return 0;
        if (siz[a] > siz[b]) fa[b] = a;
        else if (siz[b] > siz[a]) fa[a] = b;
        else fa[a] = b, siz[b]++;
        return 1;
    }
} S[19];
inline int FST(int x, int k) {
    if (!x & k > 0) return 0;
    int res = 1;
    while (k) {
        if (k & 1) res = (LL)res * x % p;
        x = (LL)x * x % p, k >>= 1;
    } return res;
}
int n, m;
int main() {
    scanf("%d%d", &n, &m);
    for (R int i = 2; i <= n; i++)
        bin[i] = bin[i >> 1] + 1;
    for (R int i = 0; i <= 18; i++)
      S[i].init(n);
    for (R int i = 1; i <= m; i++) {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        int len = b - a + 1, dex = bin[len];
        S[dex].Union(a, c);
        S[dex].Union(b - (1 << dex) + 1, d - (1 << dex) + 1);
    }
    for (R int i = bin[n]; i; i--) {
        for (R int j = 1; j + (1 << i) - 1 <= n; j++) {
            R int omg = S[i].find(j);
            S[i - 1].Union(j, omg); // 注意原来对应的点也要合并上去，不然这个合并将会没有意义 
            S[i - 1].Union(j + (1 << (i - 1)), omg + (1 << (i - 1)));
        }
    } int cnt = 0;
    for (R int i = 1; i <= n; i++)
      if (S[0].find(i) == i) ++cnt;
    printf("%d\n", 9LL * FST(10, cnt - 1) % p);
}

BZOJ 4569 萌萌哒

原文：https://www.cnblogs.com/cjc030205/p/11638103.html