【BZOJ4569】萌萌哒（并查集，倍增）

题面

BZOJ

题意：

有一个长度为\(n\)的数

给定\(m\)个限制条件

每次限制\(l1～r1\)与\(l2～r2\)是相同的

求出方案数

题解

如果每次给定的限制都是告诉你某一位和某一位是相同的

那么，我们的做法是：

并查集，然后计算有\(k\)个联通块

\(ans=9*10^{k-1}\)

但是，现在每次给定的都是一个区间

我们不太可能暴力的把区间之间的位置两两进行一次合并

所以，我们来想个办法优化一下。

试试倍增？

维护\(logn\)个并查集

第\(s\)个并查集维护一段长度为\(2^s\)的区间的相等的情况

这样，每次给定的一个相等的条件就变成了类似\(ST\)表的一次合并

但是，这样子合并了高层的显然不会影响到下面

所以，我们要下放

还是一样的，每次下放的时候都把当前的位置拆成两段

在下面的那一层对应的两个位置合并一下

最后就能够合并到了第\(0\)个并查集

然后就很容易算啦

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define MOD 1000000007

#define MAX 120000

inline int read()

{

	int x=0,t=1;char ch=getchar();

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

	if(ch=='-')t=-1,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return x*t;

}

int fpow(int a,int b)

{

	int s=1;

	while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}

	return s;

}

int n,m;

int f[20][MAX];

int lg2[MAX];

int getf(int s,int x){return f[s][x]==x?x:f[s][x]=getf(s,f[s][x]);}

void init(int s){for(int i=1;i<=n;++i)f[s][i]=i;}

void Merge(int s,int x,int y)

{

	int a=getf(s,x),b=getf(s,y);

	if(a!=b)f[s][a]=b;

}

int main()

{

	n=read();m=read();

	int cnt=0;

	for(int i=0;(1<<i)<=n;++i)init(i),cnt++;

	for(int i=2;i<=n;++i)lg2[i]=lg2[i>>1]+1;

	for(int i=1;i<=m;++i)

	{

		int l1=read(),r1=read(),l2=read(),r2=read();

		int kk=lg2[r1-l1+1];

		Merge(kk,l1,l2);

		Merge(kk,r1-(1<<kk)+1,r2-(1<<kk)+1);

	}

	for(int i=cnt;i;--i)

	{

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

		{

			Merge(i-1,j,getf(i,j));

			Merge(i-1,j+(1<<(i-1)),getf(i,j)+(1<<(i-1)));

		}

	}

	int tot=0,ans=9;

	for(int i=1;i<=n;++i)if(getf(0,i)==i)++tot;

	ans=1ll*ans*fpow(10,tot-1)%MOD;

	printf("%d\n",ans+(n==1));

	return 0;

}