BZOJ 4569 【SCOI2016】 萌萌哒

题目链接：萌萌哒

　　我先不吐槽题目名……这道题的并查集好像我们考过……既然那道题我没写就来把这道题写了吧(雾

　　这道题由于合并操作只有\(m\)次，那么很显然的一个想法就是把建一棵线段树类似物，然后每次在上面分裂区间。但是由于只有区间长度相同的才能用并查集直接维护，所以时间复杂度是\(O(m \log ^2n)\)。注意这里和下文都没有考虑并查集复杂度。

　　这样做的话我们把原序列用\(O(n)\)个区间表示了，但是每次操作是\(O(\log^2 n)\)的。如果我们找出了更多的区间，也许就可以把单词操作的复杂度降一点。事实上，我们只需要像\(st\)表那样倍增地抠区间，那么单次操作的复杂度就只有\(O(1)\)了。每次操作时分裂成两个区间，分别在并查集中并到一起就可以了。

　　最后不要忘记了把相等关系给下传。统计答案的时候注意不能有前导零。

　　下面贴代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

#define maxn 100010

#define mod 1000000007

using namespace std;

typedef long long llg;

int f[17][maxn],siz[17][maxn];

int mi[17],cnt,n,m,lo[maxn];

llg ans=1;

int getint(){

	int w=0;bool q=0;

	char c=getchar();

	while((c>'9'||c<'0')&&c!='-') c=getchar();

	if(c=='-') c=getchar(),q=1;

	while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();

	return q?-w:w;

}

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){

	int a=find(i,x),b=find(i,y);

	if(a!=b){

		if(siz[i][a]>siz[i][b]) swap(a,b);

		f[i][a]=b; siz[i][b]+=siz[i][a];

	}

}

int main(){

	File("a");

	n=getint(); m=getint(); mi[0]=1;

	for(int i=1;i<=16;i++) lo[(mi[i]=mi[i-1]<<1)+1]=i;

	for(int i=1;i<=n;i++) lo[i]=max(lo[i],lo[i-1]);

	for(int i=0;i<=lo[n];i++)

		for(int j=1;j<=n-mi[i]+1;j++)

			f[i][j]=j,siz[i][j]=1;

	while(m--){

		int l1,r1,l2,r2,t;

		l1=getint(),r1=getint();

		l2=getint(),r2=getint();

		t=lo[r1-l1+1]; merge(t,l1,l2);

		merge(t,r1-mi[t]+1,r2-mi[t]+1);

	}

	for(int i=lo[n];i>0;i--)

		for(int j=1;j<=n-mi[i]+1;j++)

			if(find(i,j)!=j){

				merge(i-1,j,find(i,j));

				merge(i-1,j+mi[i-1],find(i,j)+mi[i-1]);

			}

	for(int i=1;i<=n;i++) cnt+=(f[0][i]==i);

	for(int i=1;i<cnt;i++) ans*=10,ans%=mod;

	if(cnt) ans*=9,ans%=mod;

	printf("%lld",ans);

	return 0;

}