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=,mod=1e9+;

int n,m,l1,r1,l2,r2,tot,ans,cnt;

int mi[maxn],f[maxn][],posi[maxn*],posj[maxn*],fa[maxn*];

bool v[maxn*];

inline void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',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==)return puts(""),;

    mi[]=;for(int i=;i<=;i++)mi[i]=mi[i-]<<;

    for(int i=;i<=n;i++)

    for(int j=;j<=;j++)

    f[i][j]=++tot,posi[tot]=i,posj[tot]=j,fa[tot]=tot;

    for(int i=;i<=m;i++)

    {

        read(l1);read(r1);read(l2);read(r2);

        for(int j=;j>=;j--)

        if(l1+mi[j]-<=r1)

        {

            merge(f[l1][j],f[l2][j]);

            l1+=mi[j];l2+=mi[j];

        }

    }

    for(int j=;j;j--)

    for(int i=;i<=n;i++)

    {

        int now=gf(f[i][j]);

        int u=posi[now],v=posj[now];

        merge(f[i][j-],f[u][v-]);

        merge(f[i+mi[j-]][j-],f[u+mi[v-]][v-]);

    }

    for(int i=;i<=n;i++)if(!v[fa[f[i][]]=gf(fa[f[i][]])])v[fa[f[i][]]]=,cnt++;

    ans=;for(int i=;i<cnt;i++)ans=1ll*ans*%mod;

    printf("%d\n",ans);

}