题目描述
一个长度为 \(n\) 的大数，用 \(S_1S_2S_3 \cdots S_n\)表示，其中 \(S_i\) 表示数的第 \(i\) 位, \(S_1\) 是数的最高位。告诉你一些限制条件，每个条件表示为四个数，\(l_1,r_1,l_2,r_2\)，即两个长度相同的区间，表示子串 \(S_{l_1}S_{l_1+1}S_{l_1+2} \cdots S_{r_1}\)与 \(S_{l_2}S_{l_2+1}S_{l_2+2} \cdots S_{r_2}\)完全相同。
比如 \(n=6\) 时，某限制条件 \(l_1=1,r_1=3,l_2=4,r_2=6\) ，那么 \(123123\)，\(351351\) 均满足条件，但是 \(12012\)，\(131141\) 不满足条件，前者数的长度不为 \(6\) ，后者第二位与第五位不同。问满足以上所有条件的数有多少个。
数据范围
\(1\le n\le 10^5\)，\(1\le m\le 10^5\) ，$ 1\le li1,ri1,li2,ri2 \le n $ ；并且保证 $ r1_{i}-l1_{i}=r2_{i}-l2_{i} $ 。
solution
这题难想在用 ST 表优化并查集的合并过程（还是第一次见呢），感觉很好的例题，所以就跑来写题解了 /cy
\(f_{i, j}\) 表示以 \(i\) 为左端点，区间 \([i, j]\) 其中 \(i\) 已经完成合并的 \(i\) 的祖先（还是具体看代码理解吧 /kk）
合并就类似 ST 表预处理的方式正常合并就好了。
复杂度：\(O(nlog^2n)\)
code
/*Work by:Ariel_*/
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int mod = 1e9 + 7;
int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9'){if (c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
int N, M, f[MAXN][25];
int find(int x, int y) {return f[x][y] == x ? f[x][y] : f[x][y] = find(f[x][y], y);}
void merge(int x, int y, int len) {
int fx = find(f[x][len], len), fy = find(f[y][len], len);
f[f[fx][len]][len] = fy;
}
int main(){
N = read(), M = read();
for (int i = 1; i <= N; i++)
for (int j = 0; j <= 21; j++) f[i][j] = i;
for (int i = 1; i <= M; i++) {
int l1 = read(), r1 = read(), l2 = read(), r2 = read();
int len = log2(r1 - l1 + 1);
merge(l1, l2, len);
l1 = r1 - (1 << len) + 1, l2 = r2 - (1 << len) + 1;
merge(l1, l2, len);
}
for (int len = 21; len >= 1; len--) {
for (int i = 1; i + (1 << len) - 1 <= N; i++) {
int fa = find(i, len);
if(fa == i) continue;
merge(i, fa, len - 1);
merge(i + (1 << (len - 1)), fa + (1 << (len - 1)), len - 1);
}
}
long long Ans = 0;
for (int i = 1; i <= N; i++) {
if(f[i][0] == i) {
if(Ans == 0) Ans = 9;
else Ans = Ans * 10 % mod;
}
}
cout<<Ans;
puts("");
return 0;
}