st表

并查集 ST表
背景
小萌新∅清晰的记得教练讲过此题，只怨她自己太不努力了，模拟赛时一点也写不出来，难过。

思路
题目的限制条件是某些位置必须填一样的数字，先考虑最朴素的可行方法，对于区间 [l
1
​
,r
1
​
] 和 [l
2
​
,r
2
​
]，我们一一把对应位置加入同一集合，即合并 l
1
​
+i 和 l
2
​
+i，其中 0⩽i⩽r
1
​
−l
1
​
+1。同一集合内的所有位置，填的数字必须相同，故设 S 为集合数量，则 ans=9⋅10
S−1
，这是由于每个集合可以填 0至9 共有10种选择，含最高位的集合不能选0 只有9种选择。复杂度 O(n
2
logn)。

考虑优化，相信很多人看到此题想到的是 在线段树上做并查集，仅仅实现难度就有点大。容易发现，既然不需要在线询问，我们自然而然的想到了st表。

总思路：将询问区间拆分成 若干个小区间（不多于 logn 个），将 区间与区间 合并，最后计算答案时 将区间的信息下放到点上。

具体的来讲：fa[i][k] 表示【左端点为 位置 i，长度为 2
k
的区间】所在集合的根 的左端点

举个例子，初始所有的 fa[i][k]=i(k∈[0,logn])，将区间 [5,8] 合并到区间 [1,4]上后，有 fa[5][2]=1（区间 [1,4] 的左端点）。

最终计算答案时，将所有层的对应端点合并即可，做法是将每层和他的上层合并 即将 [i][k−1] 与 [find(i,k)][k−1] 合并，将 [i+2
k−1
][k−1] 与 [find(i,k)+2
k−1
][k−1] 合并。详见代码。复杂度 O(nlog
2
n)。

代码
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 100005, mod = 1000000007;
int n, m, fa[maxn][18], ans;
int find(int x, int k) {
return fa[x][k] == x ? x : fa[x][k] = find(fa[x][k], k);
}
void merge(int x, int y, int k) {
x = find(x, k), y = find(y, k);
if(x != y) fa[x][k] = y;
}
int main() {
scanf("%d %d", &n, &m);
const int maxk = floor(log2(n));
for(int i = 1; i <= n; ++i)
for(int k = 0; k <= maxk; ++k)
fa[i][k] = i;
for(int i = 1, l1, r1, l2, r2; i <= m; ++i) {
scanf("%d %d %d %d", &l1, &r1, &l2, &r2);
for(int k = maxk; ~k; --k)
if(l1+(1<<k)-1 <= r1) merge(l1, l2, k), l1 += 1<<k, l2 += 1<<k;
}
for(int k = maxk; k; --k)
for(int i = 1; i+(1<<k)-1 <= n; ++i) {
int pos = find(i, k);
merge(i, pos, k-1), merge(i+(1<<k-1), pos+(1<<k-1), k-1);
}
for(int i = 1; i <= n; ++i)
if(fa[i][0] == i) ans = !ans ? 9 : ans * 10ll % mod;
printf("%d\n", ans);
return 0;
}