题解 P3224 【[HNOI2012]永无乡】

Duan2baka · 2017-12-29 16:04:16 · 题解

题目大意：给你n个点，每个点有权值k，现有两种操作：将两个点所在联通块合并，查询某个点所在联通块权值第k小是哪个数

个人Blog在这里

线段树解法

这题输出的是点的编号不是点的值....

对于每个点，开个权值线段树，合并操作用并查集查找，线段树合并

查询操作是权值线段树基本操作，找第k小的数时，如果左儿子的数超过k个就在左儿子里，否则去右儿子找第k-ls->siz的数

代码如下：

#include<ctype.h>
#include<cstdio>
#define N 100050
using namespace std;
const int INF=10000000;
inline int read(){
    int x=0,f=1;char c;
    do c=getchar(),f=c=='-'?-1:f; while(!isdigit(c));
    do x=(x<<3)+(x<<1)+c-'0',c=getchar(); while(isdigit(c));
    return x*f;
}
int n,m,x,y,fx,fy,t;
int f[N],pre[N];
char s[25];
struct Node{
    int l,r,siz;
    Node *ls,*rs;
    Node();
    inline void maintain(){
        siz=ls->siz+rs->siz;
    }
}*root[N],*null;
Node::Node(){
    ls=rs=null;
}
int Find(int x){
    return f[x]==x?f[x]:f[x]=Find(f[x]);
}
inline void init(){
    null=new Node;
    null->l=null->r=-1;
    null->siz=0;
    null->ls=null->rs=null;
}
void Merge(Node *&x,Node *&y){///线段树合并
    if(y==null) return;
    if(x==null){
        x=y;
        return;
    }
    x->siz+=y->siz;
    Merge(x->ls,y->ls);Merge(x->rs,y->rs);
}
void Add(int x,int l,int r,Node *&k){
    if(k==null){
        k=new Node;
        k->l=l;k->r=r;
    }
    if(k->l==k->r){k->siz++;return;}
    int mid=k->l+k->r>>1;
    if(x<=mid) Add(x,l,mid,k->ls);
    else Add(x,mid+1,r,k->rs);
    k->maintain();
}
int Rank(int x,Node *k){
    if(k->siz<x) return -1;
    if(k->l==k->r) return k->l;
    if(x<=k->ls->siz) return Rank(x,k->ls);
    else return Rank(x-k->ls->siz,k->rs);
}
void print(Node *x){
    if(x==null) return;
    printf("%d  %d    %d\n",x->l,x->r,x->siz);
    print(x->ls);print(x->rs);
}
int main(){
    init();
    n=read();m=read();
    for(int i=1;i<=n;i++){
        f[i]=i;
        x=read();
        pre[x]=i;
        Add(x,1,INF,root[i]=null);
    }
    for(int i=1;i<=m;i++){
        x=read();y=read();
        fx=Find(x),fy=Find(y);
        if(fx==fy) continue;
        Merge(root[fx],root[fy]);
        f[fy]=fx;
    }
    m=read();
    for(int i=1;i<=m;i++){
        scanf("%s",s+1);
        if(s[1]=='B'){
            x=read();y=read();
            fx=Find(x),fy=Find(y);
            if(fx==fy) continue;
            Merge(root[fx],root[fy]);
            f[fy]=fx;
        }
        else{
            x=read();y=read();
            fx=Find(x);
            t=Rank(y,root[fx]);
            printf("%d\n",!~t?-1:pre[t]);
        }
    }
return 0;
}

Splay解法

每合并两个点，将它俩启发式合并

启发式合并，即把小的暴力往大的那里插

说按前序遍历插复杂度会极其优越？？

而求第k大是平衡树基本操作

代码如下：

#include<algorithm>
#include<ctype.h>
#include<cstdio>
#define N 100050
using namespace std;
inline int read(){
    int x=0,f=1;char c;
    do c=getchar(),f=c=='-'?-1:f; while(!isdigit(c));
    do x=(x<<3)+(x<<1)+c-'0',c=getchar(); while(isdigit(c));
    return x*f;
}
int n,m,x,y,fx,fy,t;
int f[N],pre[N];
char s[26];
int Find(int x){
    return f[x]==x?f[x]:f[x]=Find(f[x]);
}
struct Node{
    Node *ch[2],*fa;
    int x,siz;
    Node(int);
    inline int dir(){
        if(fa->ch[0]==this) return 0;
        if(fa->ch[1]==this) return 1;
        return -1;
    }
    inline void maintain(){
        siz=ch[0]->siz+ch[1]->siz+1;
        return;
    }
    inline int cmp(int k){
        if(k==x) return -1;
        return k<x?0:1;
    }
}*null,*root[N],*tmp;
Node::Node(int _):x(_){
    siz=1;
    fa=ch[0]=ch[1]=null;
}
inline void init(){
    null=new Node(-1);
    null->ch[0]=null->ch[1]=null->fa=null;
    null->siz=0;
}
void print(Node *x){///Debug
    if(x==null) return;
    printf("%d  ",x->x);
    print(x->ch[0]);
    print(x->ch[1]);
}
inline void Rotate(Node *x,int d){
    Node *k=x->ch[d^1];
    x->ch[d^1]=k->ch[d];
    if(x->ch[d^1]!=null) x->ch[d^1]->fa=x;
    k->ch[d]=x;
    if(x->fa!=null) x->fa->ch[x->dir()]=k;
    k->fa=x->fa;x->fa=k;
    x->maintain();k->maintain();
}
inline void Splay(Node *x,Node *y,int num){
    while(x->fa!=y){
        if(x->fa->fa!=y && x->dir()==x->fa->dir())
            Rotate(x->fa->fa,x->dir()^1);
        Rotate(x->fa,x->dir()^1);
    }
    x->maintain();
    if(y==null) root[num]=x;
}
void Insert(Node *&x,int k,Node *fa){
    if(x==null){
        x=new Node(k);
        x->fa=fa;tmp=x;
        return;
    }
    int d=x->cmp(k);
    Insert(x->ch[d],k,x);
    x->maintain();
}
inline void AddNew(int x,int k){
    Insert(root[x],k,null);
    Splay(tmp,null,x);
}
int K_th(int k,Node *x){
    if(k==x->ch[0]->siz+1) return x->x;
    int d=k<=x->ch[0]->siz?0:1;
    return K_th(k-(d?x->ch[0]->siz+1:0),x->ch[d]);
}
Node *LowerPointer(Node *x,int k){
    if(x==null) return null;
    if(k>=x->x) return LowerPointer(x->ch[0],k);
    Node *t=LowerPointer(x->ch[1],k);
    return t==null?x:t;
}
Node *UpperPointer(Node *x,int k){
    if(x==null) return null;
    if(k<=x->x) return UpperPointer(x->ch[1],k);
    Node *t=UpperPointer(x->ch[0],k);
    return t==null?x:t;
}
inline void Delete(int k,int x){
    Node *a=LowerPointer(root[x],k),*b=UpperPointer(root[x],k);
    if(a==null && b==null){
        root[x]=null;
        return;
    }
    if(a==null){
        Splay(b,null,x);
        root[x]->ch[0]=null;
        root[x]->maintain();
        return;
    }
    if(b==null){
        Splay(a,null,x);
        root[x]->ch[1]=null;
        root[x]->maintain();
        return;
    }
    Splay(a,null,x);
    Splay(b,a,x);
    root[x]->ch[1]->ch[0]=null;
    root[x]->ch[1]->maintain();
    root[x]->maintain();
}
inline void Merge(int tx,int ty){
    if(tx==ty) return;
    int x=tx,y=ty;
    if(root[x]->siz<root[y]->siz) swap(x,y);
    while(root[y]->siz){
        int k=K_th(1,root[y]);
        Delete(k,y);
        AddNew(x,k);
    }
    f[y]=x;
}
int main(){
    init();
    n=read();m=read();
    for(int i=1;i<=n;i++){
        f[i]=pre[x=read()]=i;
        root[i]=null;
        AddNew(i,x);
    }
    for(int i=1;i<=m;i++){
        x=read();y=read();
        x=Find(x),y=Find(y);
        Merge(x,y);
    }
    m=read();
    for(int i=1;i<=m;i++){
        scanf("%s",s+1);
        if(s[1]=='B'){
            x=read();y=read();
            Merge(Find(x),Find(y));
        }
        else{
            x=read();y=read();
            fx=Find(x);
            if(root[fx]->siz<y) printf("-1\n");
            else printf("%d\n",pre[K_th(y,root[fx])]);
        }
    }
return 0;
}