luogu P3295 [SCOI2016]萌萌哒
这里的计数没有任何的技术含量，当你知道那几个位置必须一样后，就疯狂乘 \(10\) 就可以了。
现在问题是怎么找到那几个位置必须一样。
考虑一种最暴力的方法，对于任意 \(i\ (0\leq i\leq r_1-l_1+1)\) 我们把 \(i+l_1\) 和 \(i+l_2\) 用并查集并起来。
最后显然一个集合内的位置都是相同的颜色。这样做的时间复杂度是 \(O(n^2\log n)\) 。
考虑怎么优化，想到之前学的线段树优化建图，发现不需要进行实时修改，直接用 \(\tt ST\) 表就可以了。
我们定义 \(fa(i,j)\) 表示 \([i,i+2^j-1]\) 这段区间内的根 的左端点。
也就是说我们把并查集做一个类似倍增的方法，它的父亲对应的也是一段区间，为了方便我们钦定它的父亲为根的左端点。
合并的话跟倍增几乎时一模一样。
注意到最后要把所有的相同位置拉入到一个集合，也就是对于每一层，都要和它的上一层合并。
具体的可以看一下代码。
点击查看代码
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
int n, m, lg[N];
namespace UFST {
int fa[N][20];
inline int find(int x, int k);
inline void merge(int a, int b, int k);
}
using UFST::fa;
signed main(void) {
read(n, m);
for (int i = 1, l1, l2, r1, r2; i <= m; i++) {
read(l1, r1, l2, r2);
node[i] = Node(l1, r1, l2, r2);
}
for (int i = 1; i <= n; i++)
for (int j = 0; j <= 20; j ++) fa[i][j] = i;
for (int i = 1, l1, r1, l2, r2; i <= m; i++) {
l1 = node[i].l1, r1 = node[i].r1, l2 = node[i].l2, r2 = node[i].r2;
for (int j = 20; j >= 0; j --)
if (l1 + (1 << j) - 1 <= r1) {
UFST::merge(l1, l2, j);
l1 += 1 << j; l2 += 1 << j;
}
}
for (int j = 20; j >= 1; j--) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
int pos = UFST::find(i, j);
UFST::merge(i, pos, j - 1);
UFST::merge(i + (1 << j - 1), pos + (1 << j - 1), j - 1);
}
}
int ans = 0;
for (int i = 1; i <= n; i++)
if (fa[i][0] == i) {
if (ans == 0) ans = 9;
else ans = 1ll * ans * 10 % mod;
}
std::cout << ans << std::endl;
return 0;
}
namespace UFST {
inline int find(int x, int k) {
if (fa[x][k] == x) return x;
return fa[x][k] = find(fa[x][k], k);
}
inline void merge(int a, int b, int k) {
a = find(a, k); b = find(b, k);
if (a == b) return ;
fa[a][k] = b;
}
}