zcmimi's blog

查看原题

点击跳转

可以想到用并查集维护连通块(需要数字相同区域)个数

答案就是9*连通块个数

直接对每个点维护普通的并查集太慢了

由于并查集是可以合并的,我们可以使用倍增来合并

将一个点拆成\log n个点,分别代表从点i开始长度为2^k的子串

那么当我们处理两个区间相等的关系时,对区间做二进制拆分,拆成log个区间,分别并起来即可

最后再从上(大)往下(小)连边

#include<bits/stdc++.h>
const int N=100011,P=1e9+7;
int n,m,f[21][N];
int find(int x,int k){return f[k][x]==x?x:f[k][x]=find(f[k][x],k);}
void mg(int x,int y,int k){
    x=find(x,k),y=find(y,k);
    if(x!=y)f[k][x]=y;
}
int main(){
    scanf("%d%d",&n,&m);
    int mx=log2(n);
    for(int k=0;k<=mx;++k)
        for(int i=1;i<=n;++i)
            f[k][i]=i;
    for(int i=1,a,b,c,d;i<=m;++i){
        scanf("%d%d%d%d",&a,&b,&c,&d);
        for(int k=mx;~k;--k)
            if(b-a+1>=(1<<k))
                mg(a,c,k),a+=1<<k,c+=1<<k;
    }
    for(int k=mx;k;--k)
        for(int i=1,p;i<=n-(1<<k)+1;++i)
            p=find(i,k),
            mg(i,p,k-1),mg(i+(1<<k-1),p+(1<<k-1),k-1);
    int ans=0;
    for(int i=1;i<=n;++i)
        if(f[0][i]==i)ans=!ans?9:ans*10ll%P;
    printf("%d\n",ans);
}
LG 3295 [SCOI2016]萌萌哒
comment评论
Search
search