首页 > 代码库 > BZOJ 4569 [Scoi2016]萌萌哒 ——ST表 并查集
BZOJ 4569 [Scoi2016]萌萌哒 ——ST表 并查集
好题。
ST表又叫做稀疏表，这里利用了他的性质。
显然每一个条件可以分成n个条件，显然过不了。
然后发现有许多状态是重复的，首先考虑线段树，没什么卵用。
然后ST表，可以每一层表示对应的区间大小的两个部分是否合并，如果合并就不向下递归。
然后可以剪去许多状态，变成了$O(nlogn)$的。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 100005
#define ll long long
#define md 1000000007
#define F(i,j,k) for (int i=j;i<=k;++i)
int f[maxn][21],n,m,l1,r1,l2,r2,lg[maxn];
int gf(int a,int t)
{
if (f[a][t]==a) return a;
else return f[a][t]=gf(f[a][t],t);
}
void merge(int a,int b,int t)
{
int fa=gf(a,t),fb=gf(b,t);
if (fa==fb) return ;
f[fa][t]=fb; if (!t) return ;
merge(a,b,t-1);merge(a+(1<<(t-1)),b+(1<<(t-1)),t-1);
}
int main()
{
scanf("%d%d",&n,&m);
F(i,2,n) lg[i]=lg[i>>1]+1;
F(i,1,n) F(j,0,lg[n]) f[i][j]=i;
while(m--)
{
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
int tmp=lg[r1-l1+1];merge(l1,l2,tmp);
merge(r1-(1<<tmp)+1,r2-(1<<tmp)+1,tmp);
}
int cnt=0,ans=9;
F(i,1,n) if (f[i][0]==i) cnt++; cnt--;
while(cnt--) {ans=(ll)ans*10%md;}
printf("%d\n",ans);
}
BZOJ 4569 [Scoi2016]萌萌哒 ——ST表 并查集
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。