自动搬运

查看原文

来自洛谷，原作者为

	emptysetvvvv 这里埋葬着一位 OIer 的青春

搬运于2025-08-24 21:47:26，当前版本为作者最后更新于2019-08-19 21:13:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

并查集 $\mathcal{ST}$表

背景

小萌新$\varnothing$清晰的记得教练讲过此题，只怨她自己太不努力了，模拟赛时一点也写不出来，难过。

思路

• 题目的限制条件是某些位置必须填一样的数字，先考虑最朴素的可行方法，对于区间 $[l_1,r_1]$ 和 $[l_2,r_2]$，我们一一把对应位置加入同一集合，即合并 $l_1+i$ 和 $l_2+i$，其中 $0\leqslant i\leqslant r_1-l_1+1$。同一集合内的所有位置，填的数字必须相同，故设 $S$ 为集合数量，则 $ans=9\cdot \displaystyle10^{S-1}$，这是由于每个集合可以填 $0$至$9$ 共有$10$种选择，含最高位的集合不能选$0$ 只有$9$种选择。复杂度 $O(n^2\log n)$。

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

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

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

举个例子，初始所有的 $fa[i][k]=i(k\in[0,\log n])$，将区间 $[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(n\log^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;
}