4569: [Scoi2016]萌萌哒

时间：2024-07-29 22:37:14

4569: [Scoi2016]萌萌哒

链接

分析：

　　每次给出的两个区间长度是一样的，对应位置的数字也是一样的，那么可以将两两对应的数字用并查集合并，设最后有$cnt$个不同的集合，答案就是$9\times 10 ^{cnt-1}$，第一个数不能是0。

　　暴力合并太慢了，考虑优化。对于一段区间，用倍增的思想分成log段，分别合并log段，最后的下放一下标记即可。类似线段树的懒标记。

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int mod = 1e9 + , N = ;

int f[][N], Log[N];

int find(int x,int y) {

    return f[y][x] == x ? x : f[y][x] = find(f[y][x], y);

}

void Union(int a,int b,int c) { // 合并两个段 [a,a+(1<<c)-1] 与 [b,b+(1<<c)-1]

    if (find(a, c) != find(b, c)) f[c][f[c][a]] = f[c][b];

}

int main() {

    int n = read(), m = read(), cnt = ;

    for (int i = ; i <= n; ++i) Log[i] = Log[i >> ] + ;

    for (int j = ; j <= Log[n]; ++j)

        for (int i = ; i + ( << j) -  <= n; ++i) f[j][i] = i;

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

        int a = read(), b = read(), c = read(), d = read();

        for (int j = Log[b - a + ]; ~j; --j)

            if (a + ( << j) -  <= b)

                Union(a, c, j), a += ( << j), c += ( << j);

    }

    for (int j = Log[n]; j; --j) { // 下放标记

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

            Union(i, find(i, j), j - );

            Union(i + ( << (j - )), find(i, j) + ( << (j - )), j - );

        }

    }

    for (int i = ; i <= n; ++i) if (find(i, ) == i) cnt ++;

    LL ans = ;

    for (int i = ; i < cnt; ++i) ans = ans *  % mod;

    cout << ans;

    return ;

}

相关文章