为什么我看一眼觉得像字符串,第二眼像DP呢?

有一个很朴素的暴力,就是把必须相等的数弄在一个联通块里,统计连通块数量求解即可,答案就是$9*10^{siz-1}$

可以通过$n^2$并查集来得到不错的成绩。

但是有没有一种可能可以$log~ n$时间合并区间呢?

答案是有的,就是通过倍增把区间填成一段一段的,然后对每一个$2^i$区间用并查集进行合并。

最后求解答案的时候,再把大小为$2^i$的标记下传成两段$2^{i-1}$的。妙哉!

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
#define eps 1e-8
using namespace std;
const int N=1e5+5,mod=1e9+7;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int fa[N*19],n,Log[N];bool v[N];
int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);}
void merge(int x,int y){fa[get(x)]=get(y);}
inline int calc(int x){x%=n;return !x?n:x;}
int g[19][N];
inline ll pow_mod(ll a,ll b)
{
    ll ans=1;
    for(;b;b>>=1,a=a*a%mod)
        if(b&1)ans=ans*a%mod;
    return ans;
}
int main()
{
    //freopen("moe5.in","r",stdin);
    int m;qr(n),qr(m);int cnt=0;
    for(int i=2;i<=n;i++)Log[i]=Log[i>>1]+1;
    for(int i=0;i<=Log[n];i++)
        for(int j=1;j<=n;j++){g[i][j]=++cnt;}
    for(int i=1;i<=cnt;i++)fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int l,r,len,d;qr(l),qr(r),qr(len),qr(d);
        d=len-l;len=r-l+1;
        for(int k=0;len;len>>=1,k++)
            if(len&1)
            {
                int p1=l+((len>>1)<<(k+1)),p2=p1+d;
                merge(g[k][p1],g[k][p2]);
            }
    }
    for(int i=Log[n];i;i--)
        for(int j=1;j+(1<<i)-1<=n;j++)
        {
            int f=get(g[i][j]);if(f==g[i][j])continue;
            int k=calc(f);
            merge(g[i-1][j],g[i-1][k]);merge(g[i-1][j+(1<<(i-1))],g[i-1][k+(1<<(i-1))]);
        }
    int siz=0;
    for(int i=1;i<=n;i++)
    {
        int f=get(g[0][i]),y=calc(f);
        if(!v[y]){v[y]=1;++siz;}
    }
    qw(9ll*pow_mod(10ll,siz-1)%mod);puts("");
    return 0;
}