【SCOI2016】萌萌哒

· · 题解

  传送门

  尝试写一篇能让初学倍增的新人可以看懂的题解QwQ

  O(nm) 30pts的并查集做法是橙题水平，不必赘述。

  显然从优化合并区间开始考虑

  并查集的合并是满足结合律的，就是说如果区间 A 和 B 合并，令 A' 是 A 的一个子区间， B' 是 B 的一个子区间，那么合并 A,B 可以看作合并 A',B'，合并 (A-A'),(B-B')；最后两者合并。也就是两个区间合并，分别拆成两个子区间，第一个区间和第二个区间拆出来的第一个子区间合并，拆出来的第二个子区间合并，然后两个合并完了以后再合并。拆出来的两个子区间可以有交集，但是它们的并集必须是原区间。非常绕，但这是这道题乃至许多能用倍增优化的题目的一个重要性质

  倍增显然是针对 2^k 来进行的，根据上面的性质，合并两个长度为 l 的区间，是可以拆成四个长度为 k 的区间的，满足 k 是最大的满足 2^k <= l 的整数。这样对于每个区间，它们拆出来的两个子区间的交集都等于原来的区间。这个方法在 st 表里也出现过，证明稍微想一下就明白了。

  问题变成了若干个长度为 2^k 的区间合并。既然长度是 2^k 了，不妨不向下传递，直接设 f(i,k) 是以 i 为起点长度为 2^k 的区间在并查集上的父亲，这样其实就开了 \log_2n 个并查集。每次合并的时候直接合并 f(i,k) 和 f(j,k) 就可以了

  最后我们求的显然是 k=0 这一层祖先不同的数量，所以合并完之后还要考虑怎么向下传递，即把向上合并的过程转化成向下拆分的过程。因为合并只在同一层进行（即 k 相等），那么若存在两个不同的 i,j 满足 find(i,k) = find(j,k)，说明它们在第 k 层的祖先相同，即它们连通。连通这个概念在很多题解中都有提及，我们可以将其两个区间连通视作两个区间必须完全相同（就是题目中的约束）。

  根据一开始的结合律，两个区间合并（合并完自然连通，连通一定是因为合并，两者可以视作等价），这两个区间祖先相同可以变成它们拆分后得到的四个子区间祖先相同。那么合并四个子区间就可以了，既然这里区间长度是 2 的指数，子区间长度应该直接就是 2^{k-1}。其实我们发现和上面的区间合并差不多，只是这里长度比较好做。此时我们发现就把上一层的信息传递到了下一层。

  最后传递到第一层（k=0），统计这一层几个祖先不相同的，设数量为 cnt，答案就是 9\,*\,10^{cnt-1}，这是因为第一位不能选 9。

//SCOI,2016
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN=1e5+10,MODER=1e9+7;
int n,m,fa[MAXN][30],power[30],vis[MAXN];
int l1,l2,r1,r2,cnt;
long long ans;
int find(int x,int k){
    if(fa[x][k] == x)return x;
    return fa[x][k] = find(fa[x][k],k); 
}
long long getpow(int n){
    if(n==0)return 1;
    if(n==1)return 10;
    long long tmp = getpow(n/2);
    tmp = (tmp*tmp) % MODER;
    if(n&1){
        tmp = (tmp*10)%MODER;
    }
    return tmp;
}
int main(){
    scanf("%d%d",&n,&m);
    power[0] = 1;
    for(int i=1;i<=20;i++){
        power[i] = power[i-1]<<1;
    }
    for(int idx=0;power[idx]<=n;idx++){
        for(int i=1;i+power[idx]-1<=n;i++){
            fa[i][idx] = i; //这里并查集按层，每一层祖先互不相同即可 
        }
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        int idx = log(r1-l1+1)/log(2);
        int fl1 = find(l1,idx);
        int fl2 = find(l2,idx);
        fa[fl1][idx] = fl2;
        int fr1 = find(r1-power[idx]+1,idx);
        int fr2 = find(r2-power[idx]+1,idx);
        fa[fr1][idx] = fr2;
    }
    for(int idx=log(n)/log(2);idx>=1;idx--){
        //拆分每个区间
        for(int i=1;i+power[idx]-1<=n;i++){
            int f = find(i,idx);
            if(f==i)continue;
            int fa1 = find(i,idx-1);
            int fa2 = find(f,idx-1);
            fa[fa1][idx-1] = fa2;
            fa1 = find(i+power[idx-1],idx-1);
            fa2 = find(f+power[idx-1],idx-1);
            fa[fa1][idx-1] = fa2;
        }
    }
    for(int i=1;i<=n;i++){
        int f = find(i,0);
        if(!vis[f]){
            cnt++;
            vis[f] = 1;
        }
    } 
    ans = (9 * getpow(cnt-1) )%MODER;
    printf("%lld\n",ans);
    return 0;
}