两种写法

#include<iostream>
using namespace std;
const int N=1e5+10,mod=1e9+7;
int n,m,Lg[N],fa[N][20];
int fnd(int x,int d) {
	if(fa[x][d]==x)return x;
	return fa[x][d]=fnd(fa[x][d],d);
}
void merge(int a,int b,int d) {
	a=fnd(a,d);
	b=fnd(b,d);
	if(a!=b)fa[a][d]=b;
	return;
}
int main() {
	int n,m;
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		for(int j=0; j<20; j++)fa[i][j]=i;
	}
	for(int i=0; i<m; i++) {
		int l1,r1,l2,r2;
		cin>>l1>>r1>>l2>>r2;
      
		int len=Lg[r1-l1+1];
		merge(l1,l2,len);
		merge(r1-(1<<len)+1,r2-(1<<len)+1,len);
      
//		for(int len=19;len>=0;len--){
//			if(l1+(1<<len)-1<=r1){
//				merge(l1,l2,len);
//				l1+=(1<<len);
//				l2+=(1<<len);
//			}
//		}
	}
	for(int len=19; len>0; len--) {
		for(int i=1; i+(1<<len)-1<=n; i++) {
			int fa=fnd(i,len);
			if(fa!=i) {
				merge(i,fa,len-1);
				merge(i+(1<<(len-1)),fa+(1<<(len-1)),len-1);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(fa[i][0]==i){
			if(!ans)ans=9;
			else ans=(1ll*ans*10)%mod;
		}
	}
	cout<<ans<<'\n';
	return 0;
}