分析
我们可以将一个点拆成logN个点,分别代表从点i开始,长度为2^k的子串 那么当我们处理两个区间相等的关系时,对区间做二进制拆分,拆成log个区间,分别并起来即可
当然我们这样做修改是省心了,但是同时查询的时候也会带来一些麻烦……因为,我们要求的信息是最底层的,只能是长度为1的区间,而不能有奇奇怪怪的区间 不过没关系,我们这时运用等式1,拆分并查集
具体来讲,我们从最长的区间开始逐个枚举,每次查找他和他的父亲,然后把它和父亲都劈成两半,前一半和前一半连边,后一半和后一半连边即可,这样相当于把较长区间并查集拆成两个一半的并查集
最后我们就有了一些关于那些点相等的信息,直接计算并查集个数即可
代码
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<cctype> #include<cmath> #include<cstdlib> #include<queue> #include<ctime> #include<vector> #include<set> #include<map> #include<stack> using namespace std; const int mod = 1e9+7; const int LOG = 20; int fa[LOG+2][100010],n,m,l1,l2,r1,r2,cnt; long long Ans=9; inline int sf(int x,int y){return fa[y][x]==x?x:fa[y][x]=sf(fa[y][x],y);} inline void mer(int x,int y,int k){if(sf(x,k)!=sf(y,k))fa[k][sf(x,k)]=sf(y,k);} int main(){ int i,j,k; scanf("%d%d",&n,&m); for(i=0;i<=LOG;i++) for(j=1;j<=n;j++)fa[i][j]=j; for(i=1;i<=m;i++){ scanf("%d%d%d%d",&l1,&r1,&l2,&r2); for(j=LOG;j>=0;j--) if(l1+(1<<j)-1<=r1){ mer(l1,l2,j); l1+=(1<<j); l2+=(1<<j); } } for(i=LOG;i>0;i--) for(j=1;j+(1<<i)-1<=n;j++){ mer(j,sf(j,i),i-1); mer(j+(1<<(i-1)),fa[i][j]+(1<<(i-1)),i-1); } for(i=1;i<=n;i++) if(sf(i,0)==i)cnt++; for(i=1;i<cnt;i++)Ans=Ans*10%mod; cout<<Ans; return 0; }