$bzoj4569$

$st表+并查集$

$考虑暴力方法:我们每次将对应相等的位置用并查集连起来，那么最终答案就是9*10^{连通块个数-1}$

$很明显上面这个办法过不去，问题在于重复次数太多了，如果一个区间已经对应相等了就不用再次连，用st表优化这个过程$

$每次向st表一样递归连接，分成log层，每层维护\frac{n}{logn}个并查集，代表区间，那么我们加入记忆化的思想，如果对应区间已经联通就返回，这个就是用并查集完成，否则继续递归进行这个过程。其实这里就是运用了记忆化的思想$

$那么很明显每层穿起来所有区间需要区间个数-1次，那么一共有nlogn个区间，复杂度也就是nlogn了$

$所以看见这种题就要考虑用一些方式记忆化从而降低复杂度$

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + , P = 1e9 + ;

int n, m;

int fa[][N], Log[N];

int find(int p, int x) {

    return x == fa[p][x] ? x : fa[p][x] = find(p, fa[p][x]);

}

void merge(int k, int a, int b) {

    int x = find(k, a), y = find(k, b);

    if(x == y) {

        return;

    }

    fa[k][x] = y;

    if(!k) {

        return;

    }

    merge(k - , a, b);

    merge(k - , a + ( << k - ), b + ( << k - ));

}

int main() {

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

    if(n == ) {

        puts("");

        return ;

    }

    for(int j = ; j <= ; ++j) {

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

            fa[j][i] = i;

        }

    }

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

        Log[i] = Log[i >> ] + ;

    }

    while(m--) {

        int a, b, c, d;

        scanf("%d%d%d%d", &a, &b, &c, &d);

        int t = Log[b - a + ];

        merge(t, a, c);

        merge(t, b - ( << t) + , d - ( << t) + );

    }

    long long ans = , f = ;

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

        if(find(, i) == i) {

            if(f) {

                ans = ans *  % P;

            } else {

                f = ;

            }

        }

    }

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

    return ;

}

巴特西

$bzoj4569$

最新文章

热门文章