bzoj 2733 永无乡线段树

题目:

支持两种操作:

合并两点所在的联通块

查询某点所在联通块内权值第k小.

题解

平衡树启发式合并随便搞一搞就好了。

我写了一个线段树合并

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

inline void read(int &x){

    x=0;char ch;bool flag = false;

    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;

}

const int maxn = 100010;

struct Node{

    Node *ch[2];

    int siz,id;

    void update(){

	siz = ch[0]->siz + ch[1]->siz;

    }

}*null,mem[maxn*30],*root[maxn],*it;

inline void init(){

    it = mem;null = it++;

    null->ch[0] = null->ch[1] = null;

    null->siz = 0;

}

inline Node* newNode(){

    Node *p = it++;p->ch[0] = p->ch[1] = null;

    p->siz = 0;return p;

}

inline void insert(Node* &p,int l,int r,int pos,int id){

    if(p == null) p = newNode();

    if(l == r){

	p->siz ++ ;

	p->id = id;

	return ;

    }

    int mid = l+r >> 1;

    if(pos <= mid) insert(p->ch[0],l,mid,pos,id);

    else insert(p->ch[1],mid+1,r,pos,id);

    p->update();return ;

}

inline Node* Union(Node *x,Node *y){

    if(x == null) return y;

    if(y == null) return x;

    x->ch[0] = Union(x->ch[0],y->ch[0]);

    x->ch[1] = Union(x->ch[1],y->ch[1]);

    x->update();return x;

}

int n;

inline int query(Node *p,int k){

    if(k < 1 || k > p->siz) return -1;

    int l = 1,r = n;

    while(1){

	if(l == r) return p->id;

	int mid = l+r >> 1;

	if(p->ch[0]->siz >= k){

	    p = p->ch[0];

	    r = mid;

	}else{

	    k -= p->ch[0]->siz;

	    p = p->ch[1];

	    l = mid+1;

	}

    }

}

int fa[maxn];

inline int find(int x){

    return fa[x] == x ? x : fa[x] = find(fa[x]);

}

int main(){

    init();int m;read(n);read(m);

    for(int i=1;i<=n;++i) root[i] = null,fa[i] = i;

    for(int i=1,x;i<=n;++i){

	read(x);

	insert(root[i],1,n,x,i);

    }

    for(int i=1,u,v;i<=m;++i){

	read(u);read(v);

	int x = find(u);

	int y = find(v);

	if(x == y) continue;

	fa[x] = y;

	root[y] = Union(root[x],root[y]);

    }

    int q;read(q);

    char ch;

    int x,k,u,v;

    while(q--){

	while(ch=getchar(),ch<'!');

	if(ch == 'Q'){

	    read(x);read(k);

	    int fx = find(x);

	    printf("%d\n",query(root[fx],k));

	}else if(ch == 'B'){

	    read(u);read(v);

	    int x = find(u);

	    int y = find(v);

	    if(x == y) continue;

	    fa[x] = y;

	    root[y] = Union(root[x],root[y]);

	}

    }

    return 0;

}

巴特西

bzoj 2733 永无乡线段树

题目:

题解

最新文章

热门文章

巴特西

bzoj 2733 永无乡 线段树

题目:

题解

最新文章

热门文章

bzoj 2733 永无乡线段树