T7, 8两个点

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const int N = 100010, mod = 1e9 + 7;

int f[N][31], fa[N * 30], vis[N * 30], n, m;
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); }

unordered_map<int, pii> cd;
int code(int x, int t)
{
    int cod = n * t + x;
    cd[cod] = {x, t};
    return cod;
}

ll qmi(int b, int p)
{
    ll a = 1;
    while(p)
    {
        if(p & 1) a = a * b % mod;
        p >>= 1; b = 1ll * b * b % mod;
    }
    return a;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n * 20; i ++) fa[i] = i;
    while(m --)
    {
        int l1, r1, l2, r2; scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        int len = r1 - l1 + 1;
        for(int i = 20; i >= 0; i --)
            if(len >> i & 1) 
            {
                merge(code(l1, i), code(l2, i));
                l1 += 1 << i, l2 += 1 << i;
            }
    }

    int res = 0;
    for(int k = 20; k >= 1; k --)
    {
        for(int i = 1; i <= n && i + (1 << k) - 1 <= n; i ++)
        {
            if(code(i, k) == fa[code(i, k)]) continue;
            int f = fa[code(i, k)]; auto r = cd[f]; 
            
            merge(code(i, k - 1), code(r.x, k - 1));
            merge(code(i + (1 << k - 1), k - 1), code(r.x + (1 << k - 1), k - 1));
        }
    }
    for(int i = 1; i <= n; i ++) 
        if(!vis[get(i)]) ++ res, vis[get(i)] = 1;
        
    ll ans = qmi(10, res - 1) * 9 % mod;
    cout << ans;

}