【SCOI2016】萌萌哒 题解

题目大意

  你要构造 $n$ 个数，满足 $m$ 个限制，每个限制条件给出两个长度相等的区间，表示这两个区间的数要一样。比如限制是 [1, 3] 和 [3, 5]，那 {1, 2, 1, 2, 1} 就是满足条件的。
  求方案数。
  $n \le 10^5$

题解

  这看上去，就很并查集。。。

  暴力的并查集就是对于每个限制，枚举区间的每个数，合并。

  改进一下就是用 ST 表，ST 表共 $O(\log n)$ 层，每层 $O(n)$ 个元素，给这总共 $O(n \log n)$ 个元素维护并查集。对于区间 $[l_1,r_1]$ 要跟 $[l_2,r_2]$ 合并，找到最大的 $2^t \le r_1-l_1+1$，然后在并查集上合并 $[l_1,l_1+2^t-1]$ 与 $[l_2,l_2+2^t-1]$、$[r_1-2^t+1,r_1]$ 与 $[r_2-2^t+1,r_2]$。最后从大到小遍历一遍 ST 表，对于区间 $[l,r]$，让 $[l,mid]$ 和 $[mid+1,r]$ 分别连向 $[l,r]$ 的并查集根对应的两个子区间。

相关题目

  GDOI2016 回文树：改进一下然后放到树上。（假老师出考场怒 D 这题）

代码

#include<cmath>
#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long LL;

const int maxn=1e5+5, MX=17;
const LL mo=1e9+7;

int n,m;

int ga[maxn*MX+5];
int get(int x) {return (ga[x]==x) ?x :ga[x]=get(ga[x]) ;}

int Log[maxn],bh[maxn][MX+5],sum;
void rmq_pre()
{
	fo(i,1,n) Log[i]=log(i)/log(2);
	fo(j,0,MX)
	{
		int len=1<<j;
		fo(i,1,n-len+1) bh[i][j]=++sum;
	}
	fo(i,1,sum) ga[i]=i;
}

LL mi(LL x,LL y)
{
	LL re=1;
	for(; y; y>>=1, x=x*x%mo) if (y&1) re=re*x%mo;
	return re;
}

int fir[maxn*MX+5];
int main()
{
	scanf("%d %d",&n,&m);
	
	rmq_pre();
	
	while (m--)
	{
		int l1,r1,l2,r2;
		scanf("%d %d %d %d",&l1,&r1,&l2,&r2);
		if (l1>l2) swap(l1,l2), swap(r1,r2);
		
		int t=Log[r1-l1+1];
		ga[get(bh[l2][t])]=get(bh[l1][t]);
		ga[get(bh[r2-(1<<t)+1][t])]=get(bh[r1-(1<<t)+1][t]);
	}
	
	fd(j,MX,1)
	{
		int len=1<<j;
		fo(i,1,n-len+1) if (!fir[get(bh[i][j])]) fir[get(bh[i][j])]=i; else
		{
			int x=fir[get(bh[i][j])];
			ga[get(bh[x][j-1])]=get(bh[i][j-1]);
			ga[get(bh[x+len/2][j-1])]=get(bh[i+len/2][j-1]);
		}
	}
	
	LL ans=1;
	fo(i,1,n) if (get(bh[i][0])==bh[i][0]) ans=ans*10%mo;
	ans=ans*mi(10,mo-2)%mo *9%mo;
	
	printf("%lld\n",ans);
}