有趣的倍增 ST 表题目。
题意：有一个 $n$ 位数，$m$ 个限制表示 $[l_1, r_1]$ 和 $[l_2, r_2]$ 子区间是相同的。问有多少个 $n$ 位数满足这一条件。$n, m\leq 10 ^ 5$。
容易得到区间相同是由可合并性的，考虑将这个区间划分成 $O(\log n)$ 个区间来分别拆开做。但是一个很神秘的问题是我们如果使用线段树的话，两个算然都是 $O(\log n)$ 个区间，但是他们的个数、形态不完全相同，所以不能使用线段树。
怎么办呢？直接考虑对每一个位置建 $O(\log n)$ 个节点，表示 $[pos, pos + 2 ^ k - 1]$ 区间，这样我们就可以直接合并这两个区间就可以了。不考虑并查集的复杂度，那么就是 $O(m\log n)$。
然后考虑怎么把这个下放到每一个节点。首先我们当前状态下一定只有同层可能联通，假设处理到了 $k$ 层，那么我们考虑将这些区间的左右区间分别合并在一起，然后留给 $k - 1$ 层去做。这个似乎有点像线段树的懒标记的合并啊，思路还是比较妙的。
最后时间复杂度 $O((n + m)\log n)$，可以通过。注意首位不能为 0，答案为 $9\times 10 ^ {cnt - 1}$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| int main()
{
std::cin >> n >> m;
for (int j = 0; j < L; ++ j)
for (int i = 1; i <= n - (1 << j) + 1; ++ i)
id[st[i][j] = ++ tot] = i, f[tot] = tot;
for (int i = 1, l1, r1, l2, r2; i <= m; ++ i)
{
scanf("%d %d %d %d", &l1, &r1, &l2, &r2);
int len = r1 - l1 + 1;
for (int j = 18; ~j; -- j)
if (len >> j & 1)
merge(st[l1][j], st[l2][j]), l1 += 1 << j, l2 += 1 << j;
}
for (int j = L - 1; j; -- j)
for (int i = 1; i <= n - (1 << j) + 1; ++ i)
if (find(st[i][j]) != st[i][j]) {
int x = i, y = id[find(st[i][j])];
merge(st[x][j - 1], st[y][j - 1]);
merge(st[x + (1 << (j - 1))][j - 1], st[y + (1 << (j - 1))][j - 1]);
}
int cnt = 0, res = 9;
for (int i = 1; i <= n; ++ i)
if (find(i) == i && (++ cnt) > 1) res = res * 10LL % Mod;
std::cout << res << '\n';
return 0;
}
|