HNOI2012 永无乡

发表于 | 分类于 |
字数统计: 639 字

题目链接

题解

并查集，然后利用启发式合并最多带来一个$log$的代价，暴力拆treap，然后合并。
时间复杂度$O(nlog^2 n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
struct Tr{
    Tr *ch[2];
    int r,v,siz,cnt,id;
    int cmp(int x) const {
        if(x==v)return -1;
        return x>v;
    }
    void maintain(){
        siz=cnt;
        if(ch[0]!=NULL)siz+=ch[0]->siz;
        if(ch[1]!=NULL)siz+=ch[1]->siz;
    }
};
Tr tree[1700005],*pos[400005],*root;
int S=0,n,m;
int par[100005],rk[100005]; 
void rorate_tr(Tr* &tr,int d){
    Tr *k=tr->ch[d^1];
    tr->ch[d^1]=k->ch[d];
    k->ch[d]=tr; 
    tr->maintain(),k->maintain(),tr=k;
}
void insert_tr(Tr* &tr,int x,int i_){
    if(tr==NULL){
        S++,tr=&tree[S],tr->siz=1,tr->cnt=1,tr->v=x;
        tr->ch[0]=tr->ch[1]=NULL,tr->r=rand();
        tr->id=i_;
        return ;
    }
    tr->siz++;
    if(tr->v==x){
        tr->cnt++;
    }else{
        int d=tr->cmp(x);
        insert_tr(tr->ch[d],x,i_);
        if(tr->ch[d]->r>tr->r)rorate_tr(tr,d^1);
    }
}
int Kth(Tr *tr,int x){
    if(tr==NULL||x<=0||x>tr->siz)return -1;
    int evid=(tr->ch[0]==NULL)?0:tr->ch[0]->siz;
    if(x<=evid)return Kth(tr->ch[0],x);
    else if(x>evid+tr->cnt)return Kth(tr->ch[1],x-evid-tr->cnt);
    else return tr->id;
}
int Find(int t){
    if(par[t]==t)return t;
    else return (par[t]=Find(par[t]));
}
int unite(int a,int b){
    int x=Find(a),y=Find(b);
    if(x==y)return -1;
    if(rk[x]>rk[y]){
        par[y]=x;
        return x;	
    }else {
        par[x]=y;
        if(rk[x]==rk[y])rk[y]++;
        return y;
    }
}
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}
void dfs(Tr *t){
    if(t==NULL)return ;
    insert_tr(root,t->v,t->id);
    dfs(t->ch[0]),dfs(t->ch[1]);
}
void MMerge(int x,int y){
    if(Find(x)==Find(y))return ;
    int ss=Find(x),tt=Find(y);
    int res=unite(x,y);//大的 
    if(res==tt)root=pos[tt],dfs(pos[ss]),pos[tt]=root;
    else root=pos[ss],dfs(pos[tt]),pos[ss]=root;
}	
void init(){
    n=read(),m=read();
    int pri,u,v;
    for(int i=1;i<=n;i++)
        par[i]=i,rk[i]=0,pri=read(),
        insert_tr(pos[i],pri,i);
    for(int i=1;i<=m;i++){
        u=read(),v=read();
        MMerge(u,v);
    }
}
void solve(){
    int q=read(),x,y;
    char ord[3];
    while(q--){
        scanf("%s%d%d",ord,&x,&y);
        if(ord[0]=='B')MMerge(x,y);
        else printf("%d\n",Kth(pos[Find(x)],y));
    }
}
int main(){
    init();
    solve();
    return 0;
}

Powered By Valine
v1.5.2