Brief description:

略。）

Analysis:

平衡树启发式合并。

//}/* .................................................................................................................................. */

const int N = int(1e5) + 9;

namespace SBT{
    const int NN = int(1e5) + 9;
    int c[2][NN], sz[NN], ky[NN], tot;
#define lx l[x]
#define rx r[x]
#define l c[d]
#define r c[!d]
#define kx ky[x]
#define sx sz[x]
#define d 0
    int new_node(int v = 0){
        int x=++tot;lx=rx=0;
        sx=1;kx=v;
        return x;
    }

    void upd(int x){
        sx=sz[lx]+1+sz[rx];
    }
#undef d
    void rot(int &x,int d){
        int y=rx;rx=l[y];l[y]=x;
        upd(x),upd(y),x=y;
    }

    void fix(int &x,int d){
        if (sz[l[lx]] > sz[rx]) rot(x,!d);
        else{
            if (sz[r[lx]] > sz[rx]) rot(lx,d),rot(x,!d);
            else return;
        }
        d=0,fix(lx,0),fix(rx,1);
        fix(x,0),fix(x,1);//upd(x);
    }
#define d 0

    int mini(int x){
        if (lx) return mini(lx);
        return ky[x];
    }

    void iod(int x){
        if (!x) return;
        iod(lx); printf("%d ", ky[x]); iod(rx);
    }

    void Ins(int &x,int v){
        if(!x) x = new_node(v);
        else{
            Ins(c[v>kx][x],v);
            fix(x,v>=kx);
        }
        upd(x);
    }

    void Ins2(int &x, int xx){
        if (!x) x = xx;
        else{
            Ins2(c[ky[xx]>kx][x], xx);
            fix(x, ky[xx] >= kx);
        }
        upd(x);
    }

    int d_key; void Del(int &x,int v){
        --sx;if(kx==v||(v<kx&&!lx)||(v>kx&&!rx)){
            if(!lx||!rx) d_key = kx, x = lx | rx;
            else Del(lx,v+1), kx = d_key;
        }
        else Del(c[v>kx][x],v);
    }

    int Rank(int x,int v){
        int z=0;while(x){
            if(kx<v){
                z+=sz[lx]+1;
                x=rx;
            }
            else x=lx;
        }
        return z;
    }

    int Select(int x,int k){
        if (sz[lx] == k) return x;
        return sz[lx]>k?Select(lx,k):Select(rx,k-sz[lx]-1);
    }

    bool Find(int x,int v){
        if (!x) return 0;if (kx==v) return 1;
        return Find(c[v>kx][x],v);
    }

    void Init(){
        tot = 0;
    }

    int Q[N], cz, op;

    void Merge(int x, int& y){ // x -> y
        cz = 0, op = 1; Q[cz] = x;
        while (cz < op){
            x = Q[cz++];
            if (lx) Q[op++] = lx;
            if (rx) Q[op++] = rx;
            lx = rx = 0;
            Ins2(y, x);
        }
    }

#undef d
#undef l
#undef r
#undef lx
#undef rx
#undef sx
#undef kx
} //using namespace SBT;


int T[N], P[N], sz[N]; // DSU
int n;

int Find(int x){
    return P[x] == x ? x : P[x] = Find(P[x]);
}

void Union(int x, int y){
    x = Find(x), y = Find(y); if (x == y) return;
    if (sz[T[x]] > sz[T[y]]) swap(x, y);
    P[x] = y; SBT::Merge(T[x], T[y]);
}

void Init(){
    SBT::Init(); int m; RD(n, m);
    REP_1(i, n) T[i] = SBT::new_node(RD()), P[i] = i, sz[i] = 1;
    DO(m){
        int x, y; RD(x, y);
        Union(x, y);
    }
}


int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif


    Init(); Rush{
        char cmd; int x, y;
        RC(cmd); RD(x, y);
        if (cmd == 'B'){
            Union(x, y);
        }
        else{
            x = Find(x);
            if (y > SBT::sz[T[x]]){
                OT(-1);
            }
            else{
                --y;
                OT(SBT::Select(T[x], y));
            }
        }
    }
}

References:

错的？）http://blog.sina.com.cn/s/blog_6e63f59e0101bj9b.html

Posted by xiaodao
Category: BZOJ
Tags: 启发式合并