[SCOI2016]萌萌哒

luogu
BZOJ
好神仙的倍增a
首先一个显然的想法是暴力并查集合并,最后答案=10^(并查集个数-1)*9
发现这样我们修改是\(O(nlogn)\)的,而查询只有\(o(logn)\)
大佬们想到了倍增(蒟蒻表示这根本想不到),而且是在并查集上做倍增
fa[i][j]表示区间[j,j+2^i-1]的并查集根(fa用区间左端点表示),这样修改可以拆成左右2个区间合并
但最后要统计的是fa[0][j]==j的个数
我们可以将大区间的并查集状态"传递"给小区间
具体来说:对于区间[j,j+2^i-1]和它的fa,
我们合并左区间[j,j+2^(i-1)-1]和[fa,fa+2^(i-1)-1]
合并右区间[j+2^(i-1),j+2^i-1]和[fa+2^(i-1),fa+2^i-1]
这样总复杂度\(O(nlog^2n)\)
长见识了~~

#include<bits/stdc++.h>
using namespace std;
const int _=1e5+5,p=1e9+7;
int re(){
    int x=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*w;
}
int n,m,ans;
int lg[_],fa[20][_];
int find(int k,int x){return fa[k][x]==x?x:fa[k][x]=find(k,fa[k][x]);}
void unite(int k,int x,int y){
    x=find(k,x);y=find(k,y);
    if(x^y)fa[k][x]=y;
}
int ksm(int x,int y){
    int s=1;
    while(y){if(y&1)s=1ll*s*x%p;x=1ll*x*x%p;y>>=1;}
    return s;
}
int main(){
    n=re(),m=re();
    for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
    for(int i=0;i<=lg[n];i++)
        for(int j=1;j<=n;j++)
            fa[i][j]=j;
    while(m--){
        int l1=re(),r1=re(),l2=re(),r2=re();
        int k=lg[r1-l1+1];
        unite(k,l1,l2);unite(k,r1-(1<<k)+1,r2-(1<<k)+1);
    }
    for(int i=lg[n];i>=1;i--){
        for(int j=1;j<=n;j++){
            int f=find(i,j);
            unite(i-1,j,f);unite(i-1,j+(1<<(i-1)),f+(1<<(i-1)));
        }
    }
    for(int i=1;i<=n;i++)
        if(find(0,i)==i)ans++;
    printf("%lld\n",1ll*9*ksm(10,ans-1)%p);
    return 0;
}

[SCOI2016]萌萌哒

原文：https://www.cnblogs.com/sdzwyq/p/9898568.html