[BZOJ4569][Scoi2016]萌萌哒

萌萌哒

题目大意

一个数，共n位，给你m个关系，每个关系包含\((l1,r1,l2,r2)\)，代表\(l1~r1\)，\(l2~r2\)这两个区间中的数字完全相同，求满足条件的这样的数的个数

\(nlogn\)范围

Solution

考虑一个暴力做法，我们每次把这些区间中的每个对应点都用并查集合并一下，最后直接统计联通块的个数，答案为\(9 \times 10 ^ {个数}\)

考虑倍增优化，设\(fa[x][y]\)代表以x为起点，长度为\(1<<y\)的这段区间的父亲

那么我们对于每个区间拆分成几个区间，合并完这几个区间后，我们从最长的区间开始往短的区间合并，然后不断细分，最终每一个点的父亲都可以被确定

最后一样的数联通块个数即可

code:

#include<bits/stdc++.h>
using namespace std;
const int mod=(1e9+7);
int fa[200010][21];
int getfa(int x,int y){
    return fa[x][y]==x?x:fa[x][y]=getfa(fa[x][y],y);
}
void merge(int x,int y,int len){
    x=getfa(x,len);
    y=getfa(y,len);
    if(x!=y)fa[x][len]=y;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<=20;++i){
        for(int j=1;j<=n;++j){
            fa[j][i]=j;
        }
    }
    for(int i=1;i<=m;++i){
        int l1,r1,l2,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        int x=(r1-l1+1);
        for(int j=20;j>=0;--j){
            if(x&(1<<j)){
                merge(l1,l2,j);
                l1+=(1<<j),l2+=(1<<j);
            }
        }
    }
    for(int i=20;i>=1;--i){
        for(int j=1;j+(1<<i)-1<=n;++j){
            merge(j,getfa(j,i),i-1);
            merge(j+(1<<i-1),getfa(j,i)+(1<<i-1),i-1);
        }
    }
    int ans=9;
    int num=0;
    for(int i=1;i<=n;++i){
        if(fa[i][0]==i){
            num++;
            if(num>1){
                ans=(ans*1ll*10)%mod;
            }
        }
    }
    printf("%d\n",ans);
}

[BZOJ4569][Scoi2016]萌萌哒

原文：https://www.cnblogs.com/youddjxd/p/11616126.html