「SCOI2016」萌萌哒 解题报告

「SCOI2016」萌萌哒

这思路厉害啊..

容易发现有个暴力是并查集

然后我想了半天线段树优化无果

然后正解是倍增优化并查集

有这个思路就简单了，就是开一个并查集代表每个开头\(i\)每个长\(2^j\)的区间的归属

然后合并就随便合并

最后需要\(2^0\)的信息，从上面把信息分裂传下来就好了

---

Code:

#include <cstdio>

#include <cctype>

const int N=1e5+10;

template <class T>

void read(T &x)

{

	x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

}

const int mod=1e9+7;

int n,m;

int f[N*18],Id[N][18],pos[N*20],dep[N*20],tot;

int Find(int a){return f[a]=f[a]==a?a:Find(f[a]);}

void Merge(int a,int b){f[Find(b)]=Find(a);}

int main()

{

	read(n),read(m);

	for(int j=0;j<=17;j++)

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

			Id[i][j]=++tot,f[tot]=tot,pos[tot]=i,dep[tot]=j;

	for(int l1,r1,l2,r2,i=1;i<=m;i++)

	{

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

		int d=r1+1-l1;

		for(int j=0;j<=17;j++)

			if(d>>j&1)

				Merge(Id[l1][j],Id[l2][j]),l1+=1<<j,l2+=1<<j;

	}

	for(int j=17;j;j--)

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

		{

			int anc=Find(Id[i][j]);

			if(anc==Id[i][j]) continue;

			int i_=pos[anc];

			Merge(Id[i][j-1],Id[i_][j-1]);

			Merge(Id[i+(1<<j-1)][j-1],Id[i_+(1<<j-1)][j-1]);

		}

	int ans=9,is=0;

	for(int i=1;i<=n;i++) if(Find(Id[i][0])==Id[i][0]) {if(is) ans=10ll*ans%mod;is=1;}

	printf("%d\n",ans);

	return 0;

}

---

2019.3.5