BZOJ 2049 洞穴勘测

分手后的思念是犯贱 2022-01-07 05:15 198阅读 0赞

LCT判断联通性  
没什么特别的。。还是一个普通的板子题，把LCT当并查集用了，只不过LCT灵活一些，还可以断边

话说自从昨天被维修数列那题榨干之后我现在写splay都不用动脑子了，，机械式的码splay23333

#include <bits/stdc++.h>
    #define INF 0x3f3f3f3f
    #define full(a, b) memset(a, b, sizeof a)
    using namespace std;
    typedef long long ll;
    inline int lowbit(int x){ return x & (-x); }
    inline int read(){
        int X = 0, w = 0; char ch = 0;
        while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }
        while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
        return w ? -X : X;
    }
    inline int gcd(int a, int b){ return a % b ? gcd(b, a % b) : b; }
    inline int lcm(int a, int b){ return a / gcd(a, b) * b; }
    template<typename T>
    inline T max(T x, T y, T z){ return max(max(x, y), z); }
    template<typename T>
    inline T min(T x, T y, T z){ return min(min(x, y), z); }
    template<typename A, typename B, typename C>
    inline A fpow(A x, B p, C lyd){
        A ans = 1;
        for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;
        return ans;
    }
    const int N = 10005;
    int n, m, tot, ch[N][2], fa[N], rev[N], st[N];
    
    int newNode(){
        fa[++tot] = 0; ch[tot][0] = ch[tot][1] = 0;
        return tot;
    }
    
    bool isRoot(int x){
        return ch[fa[x]][0] != x && ch[fa[x]][1] != x;
    }
    
    void reverse(int x){
        rev[x] ^= 1;
        swap(ch[x][0], ch[x][1]);
    }
    
    void push_down(int x){
        if(rev[x]){
            rev[x] ^= 1;
            reverse(ch[x][0]), reverse(ch[x][1]);
        }
    }
    
    void rotate(int x){
        int y = fa[x], z = fa[y], p = (ch[y][1] == x) ^ 1;
        push_down(y), push_down(x);
        ch[y][p^1] = ch[x][p], fa[ch[x][p]] = y;
        if(!isRoot(y)) ch[z][ch[z][1] == y] = x;
        fa[x] = z, fa[y] = x, ch[x][p] = y;
    }
    
    void splay(int x){
        int pos = 0; st[++pos] = x;
        for(int i = x; !isRoot(i); i = fa[i]) st[++pos] = fa[i];
        while(pos) push_down(st[pos--]);
        while(!isRoot(x)){
            int y = fa[x], z = fa[y];
            if(!isRoot(y)){
                if((ch[y][0] == x) ^ (ch[z][0] == y)) rotate(x);
                else rotate(y);
            }
            rotate(x);
        }
    }
    
    void access(int x){
        for(int p = 0; x; p = x, x = fa[x])
            splay(x), ch[x][1] = p;
    }
    
    void makeRoot(int x){
        access(x), splay(x), reverse(x);
    }
    
    int findRoot(int x){
        access(x), splay(x);
        while(ch[x][0]) x = ch[x][0];
        return x;
    }
    
    void link(int x, int y){
        makeRoot(x);
        if(findRoot(y) != x) fa[x] = y;
    }
    
    void cut(int x, int y){
        makeRoot(x), access(y), splay(y);
        fa[x] = ch[y][0] = 0;
    }
    
    bool isConnect(int x, int y){
        return findRoot(x) == findRoot(y);
    }
    
    int main(){
    
        int n = read(), m = read();
        for(int i = 1; i <= n; i ++) newNode();
        while(m --){
            char opt[20]; scanf("%s", opt);
            int x = read(), y = read();
            if(opt[0] == 'Q') printf(isConnect(x, y) ? "Yes\n" : "No\n");
            else if(opt[0] == 'C') link(x, y);
            else if(opt[0] == 'D') cut(x, y);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/onionQAQ/p/10701715.html