首页 > 其他 > 详细

bzoj4569[SCOI2016]萌萌哒(倍增+并查集)

时间:2019-03-15 22:04:15      阅读:71      评论:0      收藏:0      [点我收藏+]

标签:com   tps   修改   .com   push   show   inline   ==   位置   

题目链接

洛谷

BZOJ

解析

倍增+并查集

题目要求某些位置数字相同,不难想到把必须相同的位置用并查集合并起来,这样假设最后剩下\(x\)个集合,答案就是\(9 \cdot 10^{x - 1}\)(因为不能含前导零)

但是如果每个限制都把对应位置一一合并的话复杂度\(O(nm)\)显然不能接受

我们注意到并查集的合并操作是满足可合并性的,那么就可以考虑倍增

对于一个限制\((l1, r1, l2, r2)\),可以把两个区间拆成一系列长为\(2\)的幂的区间拼接起来

那么我们可以用 每个小区间对应合并 来描述这个限制

这启发我们把每个位置拆成\(log\)个点,分别表示这个位置开始,长度为\(2^0, 2^1,……\)的区间

对每个\(i\)(最多\(log\)个),我们维护一个并查集,\(belong_i[j] = k\)表示\([j, j + 2^i - 1]\)这个区间要和\([k, k + 2 ^i - 1]\)这个区间合并,那么最后的答案就是\(belong_0\)一共有多少个集合

现在唯一的问题就是怎么把\(belong_1,belong_2,……\)的限制在统计答案前下放到\(belong_0\)

我们考虑一层一层地处理,假设现在要下放\(belong_i[j]\)\(belong_{i - 1}\),我们先找到这一层\([j, j + 2^i - 1]\)所在集合的根\([k, k + 2^i - 1]\),下一层长度减半,我们只要考虑把这一层的区间都砍成两半就好

具体地说就是把下一层的\([j, j + 2^{i - 1} - 1]\)\([k, k + 2^{i - 1} - 1]\)合并,\([j + 2^{i - 1}, j + 2^i - 1]\)\([k + 2^{i - 1}, k + 2^i - 1]\)合并,转化成并查集的表示就是
\[ Union(belong_{i - 1}[j], belong_{i - 1}[k]), Union(belong_{i - 1}[j + 2^{i - 1}], belong_{i - 1}[k + 2^{i - 1}]) \]
于是这样我们就可以\(O(m \log n)\)加入限制,\(O(n \log n)\)下放限制,最后\(O(n)\)扫一遍\(belong_0\)统计答案了

个人对倍增原理的理解

如果某种操作满足可合并性,那么对\([l, r]\)的操作就可以转化成对
\[ [l, l + 2^{p_0}), [l + 2^{p_0}, l + 2^{p_0} + 2^{p_1}),[l + 2^{p_0} + 2^{p_1}, l + 2^{p_0} + 2^{p_1} + 2^{p_2}), ……(p0 > p1 > p2 > ……) \]
的操作合并起来,然后就可以对操作区间二进制拆分\(O(\log len)\)修改了

(丑陋的)代码

#include <cstdio>
#include <cstring>
#include <iostream>
#define MAXN 100005

typedef long long LL;
const int mod = (int)1e9 + 7;

void merge(int, int, int, int);
void push_down();
int qpower(int, int);

int N, M, ans;
struct DSU {
    int belong[18][MAXN];
    void init(int = 0);
    int find(int dep, int x) { return belong[dep][x] == x ? x : belong[dep][x] = find(dep, belong[dep][x]); }
    bool merge(int dep, int x, int y) {
        x = find(dep, x), y = find(dep, y);
        if (x == y) return 0;
        belong[dep][x] = y;
        return 1;
    }
} dsu;

int main() {
    std::ios::sync_with_stdio(0);
    std::cin >> N >> M;
    dsu.init(N);
    while (M--) {
        int l1, r1, l2, r2;
        std::cin >> l1 >> r1 >> l2 >> r2;
        merge(l1, r1, l2, r2);
    }
    push_down();
    for (int i = 1; i <= N; ++i) if (dsu.belong[0][i] == i) ++ans;
    printf("%lld\n", 9ll * qpower(10, ans - 1) % mod);

    return 0;
}
void merge(int l1, int r1, int l2, int r2) {
    for (int i = 17; i >= 0; --i)
        if ((1 << i) <= r1 - l1 + 1) {
            dsu.merge(i, l1, l2);
            l1 += (1 << i), l2 += (1 << i);
        }
}
void push_down() {
    for (int i = 17; i; --i) for (int j = 1; j + (1 << i) - 1 <= N; ++j) {
        int fa = dsu.find(i, j);
        if (fa ^ j) dsu.merge(i - 1, j, fa), dsu.merge(i - 1, j + (1 << i - 1), fa + (1 << i - 1));
    }
}
void DSU::init(int n) {
    for (int i = 17; i >= 0; --i) for (int j = 1; j + (1 << i) - 1 <= n; ++j) belong[i][j] = j;
}
int qpower(int x, int y) {
    int res = 1;
    while (y) {
        if (y & 1) res = (LL)res * x % mod;
        x = (LL)x * x % mod, y >>= 1;
    }
    return res;
}
//Rhein_E

bzoj4569[SCOI2016]萌萌哒(倍增+并查集)

标签:com   tps   修改   .com   push   show   inline   ==   位置   

原文:https://www.cnblogs.com/Rhein-E/p/10539720.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号