[BZOJ4569][SCOI2016]萌萌哒(倍增+并查集)

时间:2022-10-05 15:37:45

首先有一个显然的$O(n^2)$暴力做法,将每个位置看成点,然后将所有限制相等的数之间用并查集合并,最后答案就是9*(10^连通块的个数)。(特判n=1时就是10)。

然后比较容易想到的是,由于每次合并的是一个区间,逐个合并点过于浪费时间,考虑用线段树建图优化复杂度,但发现线段树建图并不能支持题目中的操作。

考虑常用来替代线段树的ST表,对每个点i拆成log个,[j][i]表示i~i+(2^j)-1这段区间,我们称它为i在第j层的点。

对于每个限制,将它拆成log个长度为2的次幂的区间,并分别在层内连边。

所有限制处理完后,从第log(n)层(最高层)逐层下放信息。若[j][a]与[j][b]有边,那么将[j-1][a]与[j-1][b]连边,[j-1][a+(1<<(j-1))]与[j-1][b+(1<<(j-1))]连边。当然若两个同层点已经在同一个连通块中则可以不用连边。

这样我们成功将边数降到nlog级别,且第0层能完全记录所有限制信息,最后所求的答案就是9*(10^第0层的连通块个数)。

若不考虑并查集复杂度,每个限制被拆成log个,每层中每个点只会下放两条边,共log层,故总复杂度$O((m+n)\log n)$。

 #include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef long long ll;
using namespace std; const int N=,mod=1e9+;
int n,m,sm,ans=,a,b,c,d,f[][N],lg[N]; int find(int k,int x){ return (f[k][x]==x) ? x : f[k][x]=find(k,f[k][x]); }
void uni(int k,int a,int b){ if (find(k,a)!=find(k,b)) f[k][f[k][a]]=f[k][b]; } int main(){
freopen("bzoj4569.in","r",stdin);
freopen("bzoj4569.out","w",stdout);
scanf("%d%d",&n,&m);
if (n==){ puts(""); return ; }
rep(i,,n) lg[i]=lg[i>>]+;
rep(j,,lg[n]) rep(i,,n-(<<j)+) f[j][i]=i;
rep(i,,m){
scanf("%d%d%d%d",&a,&b,&c,&d);
for (int j=lg[b-a+]; ~j; j--) if (a+(<<j)-<=b)
uni(j,a,c),a+=<<j,c+=<<j;
}
for (int j=lg[n]; j; j--) rep(i,,n-(<<j)+)
uni(j-,i,find(j,i)),uni(j-,i+(<<(j-)),f[j][i]+(<<(j-)));
rep(i,,n) if (find(,i)==i) sm++;
rep(i,,sm) ans=ans*10ll%mod;
printf("%d\n",ans);
return ;
}