题意
有一个 $n$ 位的大数，有 $m$ 个限制。
每个限制 $\left[l1, r1, l2, r2\right]$ 表示大数的 从左往右数第 $l1$ 位 到 从左往右数第 $r1$ 位，与 大数的 从左往右数第 $l2$ 位 到 从左往右数第 $r2$ 位 完全一致。
求有多少数满足限制。$1 \leq n, m \leq 10^5$
题解
并查集维护倍增结构。
假设我们有一个 $5$ 位的数，我们维护下面这个结构：
10[1, 4] 11[2, 5]
6[1, 2] 7[2, 3] 8[3, 4] 9[4, 5]
1[1, 1] 2[2, 2] 3[3, 3] 4[4, 4] 5[5, 5]解释一下，最下面一层（第三层）里，每个节点维护的区间长度为 $1$。中间一层（第二层）里，每个节点维护的区间长度为 $2$（第三层的两倍）。最上面的一层（第一层），每个节点维护的区间长度为 $4$（第二层的两倍）。
我们考虑合并 $\left[1, 3\right]$ 和 $\left[3, 5\right]$：
将 $6$ 号节点与 $8$ 号节点合并，再将 $3$ 号节点与 $5$ 号节点合并。
注意到一个性质，合并的节点都在同一层（因为长度相同）。
接下来我们考虑如何求答案。
我们可以把合并信息下传：
比如：
10[1, 4] 11[2, 5]
6[1, 2] 7[2, 3] 8[3, 4] 9[4, 5]
1[1, 1] 2[2, 2] 3[3, 3] 4[4, 4] 5[5, 5]我们把 $6$ 和 $8$ 合并了，我们就把 $1$ 和 $3$ 合并，且把 $2$ 和 $4$ 合并。这样就完成了下传。
最后注意，首位不能为 $0$。
代码
/*
* Please submit with C++14! It's best to use C++20 or higher version.
* By rbtree (https://rbtr.ee)
* Apparition (n@rbtr.ee)
* DO OR DIE
*/
#include <algorithm>
#include <cstdio>
#define AS 3 +
using namespace std;
using tp = long long;
constexpr tp Hat_N = 1e5, Hat_F = __lg(Hat_N), c_Mod = 1e9 + 7;
tp f[AS Hat_N][AS Hat_F];
tp find(tp x, tp l) { return f[x][l] == x ? x : f[x][l] = find(f[x][l], l); }
void link(tp x, tp y, tp k) { f[find(x, k)][k] = find(y, k); }
signed main() {
tp n, m, fl, tar = 0;
scanf("%lld%lld", &n, &m);
fl = __lg(n);
for (tp i = 1; i <= n; ++i) {
for (tp j = 0; j <= fl; ++j) f[i][j] = i;
}
while (m--) {
tp l1, r1, l2, r2;
scanf("%lld%lld%lld%lld", &l1, &r1, &l2, &r2);
for (tp i = fl; i >= 0; --i) {
if (l1 + (1ll << i) - 1 <= r1) {
link(l1, l2, i);
l1 += 1ll << i;
l2 += 1ll << i;
}
}
}
for (tp i = fl; i > 0; --i) {
for (tp j = 1, endj = n + 1 - (1ll << i); j <= endj; ++j) {
link(find(j, i), j, i - 1);
link(find(j, i) + (1ll << i - 1), j + (1ll << i - 1), i - 1);
}
}
for (tp i = 1; i <= n; ++i) {
if (f[i][0] == i) tar = tar ? (tar * 10 % c_Mod) : 9;
}
printf("%lld\n", tar);
return 0;
}
//*/