Description

Solution

一个非常naive的想法就是并查集暴力维护哪些集合要填一样的数，最后统计有几个集合就行了。但是这样是\(O(n^2)\)的。

可以借鉴ST表的思想，每次只合并两个区间，然后下传同类关系就行。

Code

#include 
    
     #include 
     
      #include 
      
       typedef long long ll;const int N = 1e5 + 10;const ll mod = 1e9 + 7;int fa[20][N], n, m, sz[20][N], L2[N];int find(const int &lvl, const int &x) {    return fa[lvl][x] == x ? x : fa[lvl][x] = find(lvl, fa[lvl][x]);}void merge(const int &lvl, const int &x, const int &y) {    int fx = find(lvl, x), fy = find(lvl, y);    if (fx == fy) return;    if (sz[lvl][fx] > sz[lvl][fy])        fa[lvl][fy] = fx;    else        fa[lvl][fx] = fy;    if (sz[lvl][fx] == sz[lvl][fy]) sz[lvl][fy]++;    return;}ll pow_mod(ll x, int p) {    ll ans = 1;    for (; p; p >>= 1, x = x * x % mod)        if (p & 1) ans = ans * x % mod;    return ans;}int main() {    scanf("%d%d", &n, &m);    int l1, r1, l2, r2;    for (int i = 2; i <= n; ++i) L2[i] = L2[i >> 1] + 1;    for (int i = 0; i <= L2[n] + 1; ++i)        for (int j = 1; j <= n; ++j) fa[i][j] = j;    for (int i = 1; i <= m; ++i) {        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);        int len = L2[r1 - l1 + 1];        merge(len, l1, l2);        merge(len, r1 - (1 << len) + 1, r2 - (1 << len) + 1);    }    for (int i = L2[n] + 1; i; --i) {        for (int j = 1; j <= n; ++j) {            merge(i - 1, j, find(i, j));            if (j + (1 << i - 1) <= n)                merge(i - 1, j + (1 << i - 1), find(i, j) + (1 << i - 1));        }    }    int cnt = 0;    for (int i = 1; i <= n; ++i)        if (fa[0][i] == i) cnt++;    printf("%lld\n", pow_mod(10LL, cnt - 1) * 9 % mod);    return 0;}