[SCOI2016] 萌萌哒

用并查集合并相同的点，答案为9*10^{并查集的块数-1}。

由“区间对区间的”可以联想到线段树优化之类的方法，换成倍增会更简单~

#include <bits/stdc++.h>
#define ll long long 
using namespace std;

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

int n,m,L[N],f[20][N];
int find(int i,int x) {return f[i][x]==x?x:f[i][x]=find(i,f[i][x]);}
void merge(int i,int x,int y) {f[i][find(i,x)]=find(i,y);}

int main() {
	scanf("%d%d",&n,&m);
	for(int i=2; i<=n; ++i) L[i]=L[i>>1]+1;
	for(int i=0; i<=L[n]; ++i) for(int j=1; j<=n; ++j) f[i][j]=j;
	for(int l1,r1,l2,r2; m--; ) {
		scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
		int d=L[r1-l1+1];
		merge(d,l1,l2);
		merge(d,r1-(1<<d)+1,r2-(1<<d)+1);
	}
	for(int i=L[n]; i; --i)
	for(int j=1; j+(1<<i)-1<=n; ++j) {
		int k=find(i,j);
		if(k==j) continue;
		merge(i-1,j,k);
		merge(i-1,j+(1<<(i-1)),k+(1<<(i-1)));
	}
	ll ans=9,tot=0;
	for(int i=1; i<=n; ++i) if(find(0,i)==i) tot++;
	for(int i=1; i<tot; ++i) ans=ans*10%mod;
	printf("%lld
",ans);
	return 0;
}