【LOJ】#2014. 「SCOI2016」萌萌哒

题解

这个题好妙啊

首先我们发现，如果我们可以暴力，就是把相同的元素拿并查集合起来，最后统计集合个数\(cnt\)

答案是\(9\*10^{cnt - 1}\)

然而我们做不到= =

我们可以用倍增的思想，类似st表，一次合并两个长度为\(2^l\)的区间

然后再从区间长度最长往下下放，从长到短遍历，就下放一层，之后会继续遍历到这层然后下放

最后统计集合个数，复杂度是\(O(n \log n)\)的

代码

#include <bits/stdc++.h>

//#define ivorysi

#define MAXN 100005

typedef long long int64;

typedef unsigned int u32;

using namespace std;

const int MOD = 1000000007;

int fa[MAXN * 25];

int st[MAXN][20],cnt = 0;

int log_2[MAXN],n,m;

int lc[MAXN * 25],rc[MAXN * 25];

int getfa(int x) {return x == fa[x] ? x : fa[x] = getfa(fa[x]);}

void merge(int x,int y) {

    if(getfa(x) == getfa(y)) return;

    fa[getfa(x)] = getfa(y);

}

void Init() {

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

    for(int i = 2 ; i <= n ; ++i) log_2[i] = log_2[i / 2] + 1;

    for(int j = log_2[n] ; j >= 0 ; --j) {

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

	    st[i][j] = ++cnt;

	    fa[cnt] = cnt;

	}

    }

    for(int j = 1 ; j <= log_2[n] ; ++j) {

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

	    lc[st[i][j]] = st[i][j - 1];

	    rc[st[i][j]] = st[i + (1 << j - 1)][j - 1];

	}

    }

}

void Solve() {

    int s1,e1,s2,e2;

    while(m--) {

	scanf("%d%d%d%d",&s1,&e1,&s2,&e2);

	int l = log_2[e1 - s1 + 1];

	merge(st[s1][l],st[s2][l]);

	merge(st[e1 - (1 << l) + 1][l],st[e2 - (1 << l) + 1][l]);

    }

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

	if(!lc[j] || !rc[j]) continue;

	int t;

	if((t = getfa(j)) != j) {

	    merge(lc[j],lc[t]);

	    merge(rc[j],rc[t]);

	}

    }

    int sum = 0;

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

	if(getfa(st[i][0]) == st[i][0]) ++sum;

    }

    int64 ans = 9;

    for(int i = 1 ; i < sum ; ++i) ans = ans * 10 % MOD;

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

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Init();

    Solve();

}