题解 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)。

代码

#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;
}