BZOJ 2733 永无乡

淡淡的烟草味﹌ 2022-01-07 05:17 240阅读 0赞

# splay启发式合并 #

启发式合并其实就是把集合数量小的合并到集合数量大的里去。  
怎么合并呢，直接一个一个插入就行了。。

用并查集维护连通性，find(i)可以找到所在splay的编号

这题好像还可以合并线段树来写，下次再补上。。

#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 = 100005;
    int n, m, tot, fa[N<<5], ch[N<<5][2], size[N<<5], val[N<<5], root[N], parent[N], pos[N];
    
    int find(int p){
        while(p != parent[p]) parent[p] = parent[parent[p]], p = parent[p];
        return p;
    }
    
    bool isConnect(int p, int q){
        return find(p) == find(q);
    }
    
    int init(int v, int f){
        ++tot;
        size[tot] = 1, val[tot] = v, fa[tot] = f;
        ch[tot][0] = ch[tot][1] = 0;
        return tot;
    }
    
    void push_up(int x){
        size[x] = size[ch[x][0]] + size[ch[x][1]] + 1;
    }
    
    void rotate(int x){
        int y = fa[x], z = fa[y], p = (ch[y][1] == x) ^ 1;
        ch[y][p^1] = ch[x][p], fa[ch[x][p]] = y;
        ch[z][ch[z][1] == y] = x, fa[x] = z;
        ch[x][p] = y, fa[y] = x;
        push_up(y), push_up(x);
    }
    
    void splay(int rt, int x, int goal){
        if(x == goal) return;
        while(fa[x] != goal){
            int y = fa[x], z = fa[y];
            if(z != goal){
                (ch[y][0] == x) ^ (ch[z][0] == y) ? rotate(x) : rotate(y);
            }
            rotate(x);
        }
        push_up(x);
        if(goal == 0) root[rt] = x;
    }
    
    int select(int rt, int k){
        if(!root[rt]) return 0;
        int cur = root[rt], p = size[ch[root[rt]][0]];
        while(1){
            if(p + 1 < k){
                k -= p + 1;
                cur = ch[cur][1];
            }
            else{
                if(p + 1 == k) return val[cur];
                cur = ch[cur][0];
            }
            p = size[ch[cur][0]];
        }
    }
    
    void insert(int rt, int x){
        if(!root[rt]){
            root[rt] = init(x, 0);
            return;
        }
        int cur = root[rt];
        while(ch[cur][x > val[cur]]){
            if(val[cur] == x) break;
            cur = ch[cur][x > val[cur]];
        }
        if(val[cur] == x){
            splay(rt, cur, 0);
            return;
        }
        ch[cur][x > val[cur]] = init(x, cur);
        splay(rt, ch[cur][x > val[cur]], 0);
    }
    
    void dfs(int x, int y){
        if(!x) return;
        dfs(ch[x][0], y);
        dfs(ch[x][1], y);
        insert(y, val[x]);
    }
    
    void merge(int x, int y){
        int fx = find(x), fy = find(y);
        if(fx == fy) return;
        if(size[root[fx]] > size[root[fy]]) swap(fx, fy);
        parent[fx] = fy;
        dfs(root[fx], fy);
    }
    
    int main(){
    
        n = read(), m = read();
        for(int i = 0; i <= n; i ++) parent[i] = i;
        for(int i = 1; i <= n; i ++){
            int v = read();
            root[i] = init(v, 0);
            pos[v] = i;
        }
        for(int i = 0; i < m; i ++){
            int x = read(), y = read();
            if(isConnect(x, y)) continue;
            merge(x, y);
        }
        int q = read();
        while(q --){
            char opt[5]; scanf("%s", opt);
            int x = read(), y = read();
            if(opt[0] == 'B'){
                if(isConnect(x, y)) continue;
                merge(x, y);
            }
            else if(opt[0] == 'Q'){
                if(size[root[find(x)]] < y) printf("-1\n");
                else printf("%d\n", pos[select(find(x), y)]);
            }
        }
        return 0;
    }

写个下动态开点的权值线段树，为啥跑出来比splay还要慢啊！这么玄学的吗。。

#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 = 100005;
    int n, m, tot;
    int tree[N<<5], root[N], lc[N<<5], rc[N<<5], pos[N], parent[N];
    
    int find(int p){
        while(p != parent[p]) parent[p] = parent[parent[p]], p = parent[p];
        return p;
    }
    
    int build(){
        ++tot;
        tree[tot] = lc[tot] = rc[tot] = 0;
        return tot;
    }
    
    void push_up(int x){
        tree[x] = tree[lc[x]] + tree[rc[x]];
    }
    
    void modify(int rt, int l, int r, int k){
        if(l == r){
            tree[rt] ++;
            return;
        }
        int mid = (l + r) >> 1;
        if(k <= mid){
            if(!lc[rt]) lc[rt] = build();
            modify(lc[rt], l, mid, k);
        }
        else{
            if(!rc[rt]) rc[rt] = build();
            modify(rc[rt], mid + 1, r, k);
        }
        push_up(rt);
    }
    
    int merge(int x, int y, int l, int r){
        if(!x) return y;
        if(!y) return x;
        if(l == r){
            tree[x] += tree[y];
            return x;
        }
        int mid = (l + r) >> 1;
        lc[x] = merge(lc[x], lc[y], l, mid);
        rc[x] = merge(rc[x], rc[y], mid + 1, r);
        push_up(x);
        return x;
    }
    
    int query(int rt, int l, int r, int k){
        if(l == r) return l;
        int mid = (l + r) >> 1;
        if(k <= tree[lc[rt]]) return query(lc[rt], l, mid, k);
        return query(rc[rt], mid + 1, r, k - tree[lc[rt]]);
    }
    
    int main(){
    
        n = read(), m = read();
        for(int i = 0; i <= n; i ++) parent[i] = i;
        for(int i = 1; i <= n; i ++){
            int v = read();
            pos[v] = i, root[i] = build(), modify(root[i], 1, n, v);
        }
        for(int i = 0; i < m; i ++){
            int x = read(), y = read();
            int fx = find(x), fy = find(y);
            if(fx == fy) continue;
            parent[fy] = fx;
            root[fx] = merge(root[fx], root[fy], 1, n);
        }
        int q = read();
        while(q --){
            char opt[10]; scanf("%s", opt);
            if(opt[0] == 'B'){
                int x = read(), y = read();
                int fx = find(x), fy = find(y);
                if(fx == fy) continue;
                parent[fy] = fx;
                root[fx] = merge(root[fx], root[fy], 1, n);
            }
            else if(opt[0] == 'Q'){
                int x = read(), k = read();
                if(tree[root[find(x)]] < k) printf("-1\n");
                else printf("%d\n", pos[query(root[find(x)], 1, n, k)]);
            }
        }
        return 0;
    }

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