题解 P3295 【[SCOI2016]萌萌哒】
emptysetvvvv
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)$。
### 代码
```cpp
#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;
}
```