题目
传送门
Sol
首先可以想到暴力并查集，直接把区间内每个数一一合并，最后求一遍联通块的个数乘法原理即可
但显然会TLE，怎么办？
最开始我想的是开线段树，每个区间分成log个后把线段树上对应节点的集合一一合并，后来发现太麻烦。。。而且好像还有问题。。。
这个时候只能Orz yyb用倍增加并查集来做
把区间拆成log个，最后用类似下放lazy的方法把子区间也一一对应合并区间
# include <bits/stdc++.h>
# define RG register
# define IL inline
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int _(1e5 + 10), Zsy(1e9 + 7);IL ll Read(){RG ll x = 0, z = 1; RG char c = getchar();for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);return x * z;
}int n, m, fa[20][_], ans = 9, lg[_], tot;IL int Find(RG int c, RG int x){ return x == fa[c][x] ? x : fa[c][x] = Find(c, fa[c][x]); }IL void Merge(RG int c, RG int x, RG int y){ RG int fx = Find(c, x), fy = Find(c, y); if(fx != fy) fa[c][fx] = fy; }int main(RG int argc, RG char* argv[]){n = Read(); m = Read();if(n == 1) return puts("10"), 0;for(RG int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;for(RG int j = 0; j <= lg[n]; ++j)for(RG int i = 1; i <= n; ++i) fa[j][i] = i;for(RG int i = 1; i <= m; ++i){RG int l1 = Read(), r1 = Read(), l2 = Read(), r2 = Read(), lg2 = lg[r1 - l1 + 1];Merge(lg2, l1, l2); Merge(lg2, r1 - (1 << lg2) + 1, r2 - (1 << lg2) + 1);}for(RG int j = lg[n]; j; --j)for(RG int i = 1; i <= n; ++i){RG int ff = Find(j, i);Merge(j - 1, i, ff), Merge(j - 1, i + (1 << (j - 1)), ff + (1 << (j - 1)));}for(RG int i = 1; i <= n; ++i) if(fa[0][i] == i) ++tot;for(RG int i = 1; i < tot; ++i) ans = 1LL * ans * 10 % Zsy;printf("%d\n", ans);return 0;
}
