bzoj4569: [Scoi2016]萌萌哒（ST表+并查集）
好喵喵的题
将一个要求用ST表分割成logn个要求，如果把f[i][j]和f[u][v]在同一个集合，那么f[i][j-1]和f[u][v-1]，f[i+2^(j-1)][j-1]和f[u][u+2^(v-1)][v-1]就并到同一个集合，最后只需要计算f[i][0]不同的集合数cnt，则答案为9*10^(cnt-1)
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int maxn=200010,mod=1e9+7; int n,m,l1,r1,l2,r2,tot,ans,cnt; int mi[maxn],f[maxn][20],posi[maxn*20],posj[maxn*20],fa[maxn*20]; bool v[maxn*20]; inline void read(int &k) { int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f; } int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);} void merge(int x,int y){x=gf(x);y=gf(y);fa[x]=y;} int main() { read(n);read(m); if(n==1)return puts("10"),0; mi[0]=1;for(int i=1;i<=18;i++)mi[i]=mi[i-1]<<1; for(int i=1;i<=n;i++) for(int j=0;j<=18;j++) f[i][j]=++tot,posi[tot]=i,posj[tot]=j,fa[tot]=tot; for(int i=1;i<=m;i++) { read(l1);read(r1);read(l2);read(r2); for(int j=18;j>=0;j--) if(l1+mi[j]-1<=r1) { merge(f[l1][j],f[l2][j]); l1+=mi[j];l2+=mi[j]; } } for(int j=18;j;j--) for(int i=1;i<=n;i++) { int now=gf(f[i][j]); int u=posi[now],v=posj[now]; merge(f[i][j-1],f[u][v-1]); merge(f[i+mi[j-1]][j-1],f[u+mi[v-1]][v-1]); } for(int i=1;i<=n;i++)if(!v[fa[f[i][0]]=gf(fa[f[i][0]])])v[fa[f[i][0]]]=1,cnt++; ans=9;for(int i=1;i<cnt;i++)ans=1ll*ans*10%mod; printf("%d ",ans); }