LOJ2014 SCOI2016 萌萌哒 并查集、ST表优化连边

传送门

一个朴素的做法就是暴力连边并查集，可是这是\(O(n^2)\)的。发现每一次连边可以看成两个区间覆盖，这两个区间之间一一对应地连边。可线段树对应的两个节点的size可能不同，这会导致“一一对应”的条件在线段树上失效。所以我们需要使用ST表来完成连边。

对原序列建好ST表，对于每一个修改将两个区间覆盖到ST表上然后两两之间连边。注意在ST表上连边的两个区间要对应，即如果ST表上对应\([l,r]\)的区间与对应\([L,R]\)的区间连了边，意味着对于\(\forall i \in [0 , r - l],\)有边\((l + i , L + i)\)。

这样连边的复杂度是\(O(nlogn)\)的，但是查询就比较麻烦了，因为我们并查集只能查询大小为\(1\)的区间，而不能混入这些奇奇怪怪的区间。

但是我们可以把每一层ST表对应的并查集向下传，直到传到最底层。具体来说从上往下遍历每一层ST表对应的并查集，找到第\(i\)个点和它在这一层并查集上的根。这两个点在下一层的ST表中分别对应两个点，而连边的时候又是对应的，所以将它们的左儿子之间连边、右儿子之间连边即可。

总复杂度\(O(nlogn)\)

#include<iostream>
#include<cstdio>
#include<cctype>
#include<algorithm>
//This code is written by Itst
using namespace std;

inline int read(){
    int a = 0;
    char c = getchar();
    while(!isdigit(c))
        c = getchar();
    while(isdigit(c)){
        a = a * 10 + c - 48;
        c = getchar();
    }
    return a;
}

const int MAXN = 100007 , MOD = 1e9 + 7;
int ST[19][MAXN];
int N , M , cnt , logN , head[MAXN << 3] , dir[MAXN * 20] , fa[MAXN * 20];

void init(){
    for(logN = 0 ; 1 << logN <= N ; ++logN)
        for(int j = 1 ; j + (1 << logN) - 1 <= N ; ++j){
            ST[logN][j] = ++cnt;
            dir[cnt] = j;
            fa[cnt] = cnt;
        }
    --logN;
}

int find(int a){return fa[a] == a ? a : (fa[a] = find(fa[a]));}

void merge(int a , int b){fa[find(a)] = find(b);}

inline void add(int a , int b , int len){
    for(int i = 18 ; i >= 0 ; --i)
        if(len & (1 << i)){
            merge(ST[i][a] , ST[i][b]);
            a += 1 << i;
            b += 1 << i;
        }
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    //freopen("out","w",stdout);
#endif
    N = read(); M = read();
    init();
    for(int i = 1 ; i <= M ; ++i){
        int a = read() , b = read() , c = read();
        read();
        add(a , c , b - a + 1);
    }
    for(int i = logN ; i ; --i)
        for(int j = 1 ; j + (1 << i) - 1 <= N ; ++j){
            int t = find(ST[i][j]);
            if(t != ST[i][j]){
                int x = dir[t];
                merge(ST[i - 1][j] , ST[i - 1][x]);
                merge(ST[i - 1][j + (1 << i - 1)] , ST[i - 1][x + (1 << i - 1)]);
            }
        }
    bool f = 0;
    int ans = 1;
    for(int i = 1 ; i <= N ; ++i)
        if(fa[i] == i){
            ans = ans * (9ll + f) % MOD;
            f = 1;
        }
    cout << ans;
    return 0;
}

LOJ2014 SCOI2016 萌萌哒 并查集、ST表优化连边

原文：https://www.cnblogs.com/Itst/p/10453216.html