【ST表】SCOI2016 萌萌哒

题目内容

洛谷链接

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

输入格式

第一行两个数\(n\)和\(m\)，分别表示大数的长度，以及限制条件的个数。接下来\(m\)行，对于第\(i\)行,有4个数\(l_{i1}，r_{i1}，l_{i2}，r_{i2}\)，分别表示该限制条件对应的两个区间。

\(1≤n≤10^5，1≤m≤10^5，1≤l_{i1},r_{i1},l_{i2},r_{i2}≤n\)

并且保证\(r_{i1}-l_{i1}=r_{i2}-l_{i2}\)。

输出格式

一个数，表示满足所有条件且长度为\(n\)的大数的个数，答案可能很大，因此输出答案模\(10^9+7\)的结果即可。

样例输入

4 2

1 2 3 4

3 3 3 3

样例输出

90

思路

并查集+ST表，利用倍增合并集合。

代码

#include <cmath>

#include <cstdio>

using namespace std;

const int maxn=1e5+10;

const int Mod=1e9+7;

int n,m;

int fa[maxn][20];//表示[i,i+2^j-1]

long long ans;

void init(int k){

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

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

            fa[i][j] = i;

}

int find(int x, int y){

    return x==fa[x][y] ? x : (fa[x][y]=find(fa[x][y],y));

}

void merge(int x, int y, int j){

    int fx=find(x,j),fy=find(y,j);

    if((fx!=fy))fa[x][j]=y;

}

int main() {

    scanf("%d %d", &n, &m);

    int maxj = floor(log2(n));//求一下最大倍增次数，也可以直接用20

    init(maxj);

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

        int l1,r1,l2,r2;

        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);

        for (int j=maxj;j!=-1;--j)

            if (l1+(1<<j)-1<=r1){

                merge(l1,l2,j);

                l1+=1<<j;

                l2+=1<<j;

            }

    }

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

        for (int i=1;i+(1<<j)-1<=n;++i) {

            int fath=find(i,j);

            merge(i,fath,j-1);

            merge(i+(1<<j-1),fath+(1<<j-1),j-1);

        }

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

        if (fa[i][0]==i)ans=!ans ? 9 : ans*10%Mod;

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

    return 0;

}

巴特西