Luogu

BZOJ

分析

先考虑每次告诉你 $i$ 和 $j$ 相等怎么做。

每次用并查集合并,设最后有 $tot$ 个连通块,答案就是 $9\times 10^{tot-1}$ 。


再来考虑 $[l_1,r_1]$ 向 $[l_2,r_2]$ 连边怎么做。

(神仙操作开始)

考虑倍增。维护 $\log n+1$ 个并查集,第 $i$ 个并查集中的第 $j$ 个元素表示区间 $[j,j+2^i-1]$ 。

合并两个区间时,类似于 $\mathrm{ST}$ 表,拆成两个区间分别合并。

现在合并了高层,还要将合并关系下放。

与上面类似,每次下放把当前的位置拆成两端,在下面一层对应的两个位置合并就行了。

最后到第 $0$ 个并查集中统计一下连通块数,答案就是 $9\times 10^{tot-1}$ 。

具体实现及细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;
const int mod=1e9+7;

int n,m;
int f[20][N];
int lg[N];

inline int find(int s,int x) { return f[s][x]==x?x:f[s][x]=find(s,f[s][x]); }
inline void merge(int s,int x,int y) {
    x=find(s,x),y=find(s,y);
    if (x!=y) f[s][x]=y;
}

inline int qpow(int a,int b) {
    int ans=1;
    for (;b;b>>=1,a=1ll*a*a%mod)
        if (b&1) ans=1ll*ans*a%mod;
    return ans;
}

int main() {
    n=read(),m=read();
    for (re int i=2;i<=n;++i) lg[i]=lg[i>>1]+1;
    for (re int i=0;i<=lg[n];++i)
        for (re int j=1;j<=n;++j) f[i][j]=j;
    for (re int i=1;i<=m;++i) {
        int l1=read(),r1=read(),l2=read(),r2=read();
        int t=lg[r1-l1+1];
        merge(t,l1,l2),merge(t,r1-(1<<t)+1,r2-(1<<t)+1);
    }
    for (re int i=lg[n];i;--i) {
        for (re int j=1;j+(1<<i)-1<=n;++j) {
            merge(i-1,j,find(i,j));
            merge(i-1,j+(1<<(i-1)),find(i,j)+(1<<(i-1)));
        }
    }
    int tot=0;
    for (re int i=1;i<=n;++i)
        if (find(0,i)==i) ++tot;
    printf("%d\n",9ll*qpow(10,tot-1)%mod);
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 28 PM