BZOJ4569 [SCOI2016]萌萌哒

题意

一个长度为$n$的大数,用$S_1S_2S_3…S_n$表示,其中$S_i$表示数的第$i$位,$S_1$是数的最高位。告诉你$m$个限制条件,每个条件表示为四个数,$l_1,r_1,l_2,r_2$,即两个长度相同的区间,表示子串$S_{l_1}S_{l_1+1}S_{l_1+2}…S_{r_1}$与$S_{l_2}S_{l_2+1}S_{l_2+2}…S_{r_2}$完全相同。比如$n=6$时,某限制条件$l_1=1,r_1=3,l_2=4,r_2=6$,那么$123123$,$351351$均满足条件,但是$12012$,$131141$不满足条件,前者数的长度不为$6$,后者第二位与第五位不同。问满足以上所有条件的数有多少个。
$1 \leqslant n,m \leqslant 1e5$。

题解

看到这种一些数与另一些数相同,容易让人想到并查集。但是并查集暴力连边会T掉,该怎么办呢?我们考虑一种神奇的操作:即用ST表来维护并查集。开$logn$个并查集维护ST表中每一层的情况。其中第$i$层的并查集中有一条$x$到$y$的边,表示区间[x,x+(1<<i)-1]与区间[y,y+(1<<i)-1]中的每个数都相同。每次加入一个限制条件,只需在对应的并查集上连边即可。最后统计答案时,把每一层的连边下传。若最后一层的联通块个数为$sum$,那么答案就是$9 \times 10^{sum}$啦~注意特判一下$n=1$的情况。
时间复杂度$O(nlog(n) \alpha(n))$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF=1e9;
const long double eps=1e-9;
const int maxn=1e5+10;
const int mod=1e9+7;
const int maxsz=20;
int logn[maxn];
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
struct DSU{
int fa[maxn];
inline void Initialize(int n){
int i;
for(i=1;i<=n;i++)fa[i]=i;
}
int Find(int x){
return fa[x]==x ? x : fa[x]=Find(fa[x]);
}
inline void Merge(int x,int y){
int u=Find(x),v=Find(y);
if(u!=v)fa[u]=v;
}
}T[maxsz];
int main(){
int i,j,k,m,n;
#ifndef ONLINE_JUDGE
freopen("BZOJ4569.in","r",stdin);
freopen("BZOJ4569.out","w",stdout);
#endif
n=read();m=read();
int cnt=0;
for(i=1;i<=(n<<1);i<<=1)T[cnt++].Initialize(n);
for(i=2;i<=n;i++)logn[i]=logn[i>>1]+1;
for(i=1;i<=m;i++){
int l1,l2,r1,r2;
l1=read();r1=read();l2=read();r2=read();
T[logn[r1-l1+1]].Merge(l1,l2);
T[logn[r1-l1+1]].Merge(r1-(1<<logn[r1-l1+1])+1,r2-(1<<logn[r1-l1+1])+1);
}
for(i=cnt;i;i--)
for(j=1;j+(1<<i)-1<=n;j++){
T[i-1].Merge(j,T[i].Find(j));
T[i-1].Merge(j+(1<<(i-1)),T[i].Find(j)+(1<<(i-1)));
}
int sum=0;ll ans=1;
for(i=1;i<=n;i++)
if(T[0].Find(i)==i)sum++;
for(i=1;i<sum;i++)(ans*=10)%=mod;
ans=ans*9%mod;
printf("%lld\n",ans+(n==1));
return 0;
}