[bzoj4569]-[SCOI2016]萌萌哒

题目（bzoj）
题目（洛谷）
 
来说说这题吧
首先一看题就知道这提要求个并查集，然后答案就是9x10^(cnt-1)，其中cnt为集合个数。
为啥？首先这些限制就是要你合并一些集合，数字的第一位不能取0，剩下的就可以取0，所以一开始乘个⑨，后面就一直乘10.
然后呢？直接搞并查集O(n^2)毫不留情T掉，我们考虑倍增。
...为什么会考虑倍增？首先，并查集是可以合并的，于是利用线段树那种思想，将一个区间划分成左右两区间，然后划分到区间大小为1时再往上慢慢合并，可以证明每次操作是log(len)的，其中len为该区间大小。
于是这题就出来了：设p[x][i]表示从x开始走2^i所能到达的点，这样就可以操作了。

#include <bits/stdc++.h>
using namespace std;
template <class _E> inline void read(_E &e){
	e=0;bool ck=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
	while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
	if(ck)e=-e;
}
typedef long long ll;
const int N=100050;
const ll mod=1e9+7;
int n,m;
ll mi(ll a,ll b){
	ll ret=1;
	while(b){
		if(b&1)ret=((re
		b>>=1;
		a=((
	}
	return re
}
struct options{
	int l1,r1,l2,r2,len;
}e[N];
int cnt,f[N*20],p[N][20],L[N*20],R[N*20];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
void chushi(){
	cnt=0;
	for(int j=0;j<=18;++j){
		if((1<<j)>n)break;
		for(int i=1;i+(1<<j)-1<=n;++i){
			p[i][j]=++cnt;
			if(!j)continue;
			L[cnt]=p[i][j-1];
			R[cnt]=p[i+(1<<(j-1))][j-1];
		}
	}
	for(int i=1;i<=cnt;++i)f[i]=i;
}
inline void mergef(int x,int y){
	int px=find(x),py=find(y);
	if(px!=py)f[px]=py;
}
void solve(){
	for(int i=1;i<=m;++i){
		mergef(p[e[i].l1][e[i].len],p[e[i].l2][e[i].len]);
		mergef(p[e[i].r1-(1<<e[i].len)+1][e[i].len],p[e[i].r2-(1<<e[i].len)+1][e[i].len]);
	}
	for(int i=cnt;i>n;--i){
		int px=find(i);
		if(px!=i)mergef(L[i],L[px]),mergef(R[i],R[px]);
	}
	int tmp=0;
	for(int i=1;i<=n;++i){
		tmp+=((find(i))==i);
	}
	ll ans=9;
	ans=ans*(ll)mi(10,tmp-1
	printf(
}
int main(){
	read(n),read(m);
	chushi();
	for(int i=1;i<=m;++i){
		read(e[i].l1),read(e[i].r1);
		read(e[i].l2),read(e[i].r2);
		e[i].len=log((double)(e[i].r1-e[i].l1+1))/log(2.0);
	}
	solve();
	return 0;
}