萌萌哒

ST 表思想优化并查集合并。

好了，其实是这道题的题目叫萌萌哒。

题源：P3295 SCOI2016 萌萌哒 - 洛谷。

题解

题意：每次给定字符串的两个区间相同，问有多少种可能的字符串（仅由数字构成）。

朴素想法：每次给定两个区间，将所有对应相同的字符通过并查集合并。最后计算有多少个集合，每个集合有 10 种取值（除第一位所在的集合不能取 0，有 9 种取值），乘法原理即可。

但这样处理的时间复杂度为 $O(mn)$ ，不考虑并查集操作的时间复杂度。

于是考虑使用 ST 表的思想来优化每次合并。

构建并查集时，建立 $log_2(n) + 1$ 层节点，其中，第 $k$ 层的节点 $i$ 表示以 $i$ 为左端点的长度为 $2^k$ 的一段区间。这样，合并两段区间时，就可以仿照 ST 表的处理，分别合并两对长度为 $2^k$ 的区间。

所有合并处理完后，将所有层的合并逐层下放（第 $k$ 层的合并拆解为两个 $k-1$ 层的合并），完成到单个字符上，最后计数有多少个集合即可。时间复杂度 $O(n\log n)$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;

constexpr int mod = 1e9 + 7;

int qmi(int a, int k, int p){
    int res = 1;
    while(k){
        if(k & 1) res = res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}

void solve(){
    int n, m; cin >> n >> m;

    vector<int>lg(n + 1);
    for(int i = 2; i <= n; i++){
        lg[i] = lg[i >> 1] + 1;
    }

    vector<vector<int>>p(n, vector<int>(lg[n] + 1));
    for(int j = 0; j <= lg[n]; j++){
        for(int i = 0; i + (1 << j) - 1 < n; i++){
            p[i][j] = i;
        }
    }
    function<int(int, int)>find = [&](int x, int d){
        return x == p[x][d] ? x : p[x][d] = find(p[x][d], d);
    };
    auto merge = [&](int x, int y, int d){
        int fx = find(x, d), fy = find(y, d);
        if(fx == fy) return;
        p[fx][d] = fy;
    };

    for(int i = 0; i < m; i++){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a--, b--, c--, d--;
        int k = lg[b - a + 1];
        merge(a, c, k);
        merge(b - (1 << k) + 1, d - (1 << k) + 1, k);        
    }

    for(int k = lg[n]; k >= 1; k--){
        for(int i = 0; i + (1 << k) - 1 < n; i++){
            int fi = find(i, k);
            if(i == fi) continue;
            merge(i, fi, k - 1);
            merge(i + (1 << k - 1), fi + (1 << k - 1), k - 1);
        }
    }

    int cnt = 0;
    for(int i = 0; i < n; i++){
        if(i == find(i, 0)) cnt++;
    }

    cout << 9 * qmi(10, cnt - 1, mod) % mod << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}