题目

有一个长度为\(n\)的十进制数，用\(s\)表示。有\(m\)个限制条件，每个条件形如：\((l_1,r_1,l_2,r_2)\)，表示\(s[l_1:r_1]=s[l_2:r_2]\)。

现在给出这些限制条件，问有多少个数满足条件。

\(n,m\le 10^5\) 。

分析

这个题这是神奇！！

首先如果暴力的话，那么我们是把每一个条件的每一个对应位用并查集并起来，最后统计集合的个数\(x\)，就可以用\(9*10^{x-1}\)来计算答案了（第一位所在的集合只能填1-9）。

然而限制条件数特别多，暴力显然是不行的。最开始想的是线段树，然而不会做。

考虑类似ST表的方法，我们把这个区间划分成前\(2^j\)位和后\(2^j\)位，那么就变成了这两端\(2^j\)位分别对应相同。我们开\(\log n\)个并查集，每一层记录对应\(j\)的相同性，我们就可以快速处理完每个条件了。

处理完所有条件之后，我们会得到\(\log n\)个并查集，第\(j\)个并查集的\(x,y\)在同一个集合中就表示\(s[x:x+2^j-1]=s[y:y+2^j-1]\)。我们从上往下（\(j\)从大到小）把这个相同性推到下一层去，就可以在总时间\(O((n+m)\log n\cdot \alpha (n))\)的复杂度内得到最后的并查集。最后扫一遍得到集合数即可。

这题中先用ST表思想处理条件，最后统计的方法是很妙的。

代码

#include<cstdio>

#include<cctype>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long giant;

int read() {

    int x=0,f=1;

    char c=getchar();

    for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;

    for (;isdigit(c);c=getchar()) x=x*10+c-'0';

    return x*f;

}

const int maxn=1e5+1;

const int maxj=17;

const int q=1e9+7;

int bin[maxn],n;

inline int Multi(int x,int y) {return (giant)x*y%q;}

inline int mi(int x,int y) {

    int ret=1;

    for (;y;y>>=1,x=Multi(x,x)) if (y&1) ret=Multi(ret,x);

    return ret;

}

struct SET {

    int f[maxn];

    void init(int n) {for (int i=1;i<=n;++i) f[i]=i;}

    int find(int x) {return f[x]==x?x:f[x]=find(f[x]);}

    int merge(int x,int y) {

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

        if (fx!=fy) f[fx]=fy;

    }

} st[maxj];

int main() {

#ifndef ONLINE_JUDGE

    freopen("test.in","r",stdin);

#endif

    n=read();

    for (int i=2;i<=n;++i) bin[i]=bin[i>>1]+1;

    for (int i=bin[n];i>=0;--i) st[i].init(n);

    for (int m=read();m;--m) {

        int x=read(),y=read(),l=read(),r=read(),len=r-l+1,d=bin[len];

        st[d].merge(x,l);

        st[d].merge(y-(1<<d)+1,r-(1<<d)+1);

    }

    for (int j=bin[n];j;--j) {

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

            int p=st[j].find(i);

            st[j-1].merge(i,p);

            st[j-1].merge(i+(1<<(j-1)),p+(1<<(j-1)));

        }

    }

    int cnt=0;

    for (int i=1;i<=n;++i) cnt+=(st[0].find(i)==i);

    int ans=Multi(9,mi(10,cnt-1));

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

    return 0;

}

巴特西

bzoj4569-萌萌哒

题目

分析

代码

最新文章

热门文章