「SCOI2016」「BZOJ-4569」萌萌哒-ST表+并查集

一个长度为 $ n $ 的大数,用 $ S_1S_2S_3 \ldots 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} \ldots S_{r_1} $ 与 $ S_{l_2}S_{l_2 + 1}S_{l_2 + 2} \ldots S_{r_2} $ 完全相同。

比如 $ n = 6 $ 时,某限制条件 $ (l_1 = 1, r_1 = 3, l_2 = 4, r_2 = 6) $,那么 $ 123123 $,$ 351351 $ 均满足条件,但是 $ 12012 $,$ 131141 $ 不满足条件,前者数的长度不为 $ 6 $,后者第二位与第五位不同。问满足以上所有条件的数有多少个。

链接

BZOJ-4569

题解

引用 zyqn 的话:

这题,出题人是怎么想到的QAQ,真心服 Orz

这是一道神题啊,建立 ST 表,每层维护一个并查集。
每个信息可以拆成两条长度为 $2$ 的幂次的区间相等的信息,等价于 ST 表里两对点的合并。
然后递归合并,一旦发现已经合并过了就退出。
时间复杂度 $O(n \text{ log } n \alpha(n))$

代码

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
28
29
30
31
/*
* created by xehoth on 01-04-2017
*/
#include <bits/stdc++.h>
int n, m, a, b, c, d, f[17][100010], v[100010], ans = 9, i, j;
inline int get(int i, int j) {
return f[i][j] == j ? j : f[i][j] = get(i, f[i][j]);
}
inline void merge(int p, int x, int y) {
if (get(p, x) == get(p, y)) return;
f[p][f[p][x]] = f[p][y];
if(!p) return;
p--, merge(p, x, y), merge(p, x + (1 << p), y + (1 << p));
}
int main() {
scanf("%d%d", &n, &m);
if (n == 1) puts("10"), exit(0);
for (i = 0; (1 << i) <= n; i++)
for(j = 1; j + (1 << i) - 1 <= n; j++)
f[i][j] = j;
while(m--) {
scanf("%d%d%d%d", &a, &b, &c, &d), i = 31 - __builtin_clz(b - a + 1);
merge(i, a, c), merge(i, b - (1 << i) + 1, d - (1 << i) + 1);
}
for (v[get(0, 1)] = 1, i = 2; i <= n; i++)
if (!v[get(0,i)]) v[f[0][i]] = 1, ans = 10LL * ans % 1000000007;
return printf("%d", ans), 0;
}
分享到