Eternity

Until The End

P3224 [HNOI2012]永无乡

发表于 更新于 分类于
本文字数： 4.3k 阅读时长 ≈ 4 分钟

梦幻虚无的孤岛，永无日落的故乡。

题目链接

平衡树 + 启发式合并

用平衡树维护整个非连通块，然后暴力启发式合并。

所谓启发式合并，在并查集里的运用就是按秩合并，即合并两个集合时，将小的集合合并至大的集合。看似暴力，时间复杂度为 $\mathcal O(n^2)$ ，实际上，每一个结点的期望合并次数是 $\mathcal O(\log n)$ ，所以理论复杂度是 $\mathcal O(n\log n)$ 。

对于这道题而言，先建立 $n$ 个独立结点，然后查询和合并就可以了，用 $fa[x]$ 记录并查集里的祖先，$rt[x]$ 记录平衡树里的祖先，不要混淆了。

AC Code 
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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
const int MAXN=1e5+10;
int N,M,Q;
int Idx=0,Rt;
int x,y,z;
struct Fhq
{
    int val,rd,siz,id,chi[2];
}Tr[MAXN];
#define ls(p) Tr[p].chi[0]
#define rs(p) Tr[p].chi[1]
int Fa[MAXN],rt[MAXN];
inline int newNode(int v,int i)
{
    Tr[++Idx]=(Fhq){v,rand(),1,i};
    return Idx;
}
inline void upDate(int p)
{
    Tr[p].siz=Tr[ls(p)].siz+Tr[rs(p)].siz+1;
}
inline void split(int p,int k,int &u,int &v)
{
    if(!p) u=v=0;
    else
    {
        if(Tr[p].val<=k) u=p,split(rs(u),k,rs(u),v);
        else v=p,split(ls(v),k,u,ls(v));
        upDate(p);
    }
}
inline int merge(int u,int v)
{
    if(!u||!v) return u+v;
    if(Tr[u].rd<Tr[v].rd)
    {
        rs(u)=merge(rs(u),v);
        return upDate(u),u;
    }
    else
    {
        ls(v)=merge(u,ls(v));
        return upDate(v),v;
    }
}
inline void init(int n)
{
    for(int i=1;i<=n;++i) Fa[i]=i;
}
int getFa(int x)
{
    return Fa[x]==x?x:Fa[x]=getFa(Fa[x]);
}
inline bool check(int &x,int &y)
{
    x=getFa(x),y=getFa(y);
    return x==y;
}
void dfs(int x,int &tar)
{
    if(!x) return ;
    dfs(ls(x),tar),dfs(rs(x),tar);
    ls(x)=rs(x)=0;
    Tr[x].siz=1;
    int rt1,rt2;
    split(tar,Tr[x].val,rt1,rt2);
    tar=merge(rt1,merge(x,rt2));
}
inline void mergeSet(int x,int y)
{
    if(check(x,y)) return ;
    if(Tr[rt[x]].siz>Tr[rt[y]].siz) std::swap(x,y);
    Fa[x]=y;
    dfs(rt[x],rt[y]);
}
inline int kth(int u,int k)
{
    while(1)
    {
        if(k<=Tr[ls(u)].siz) u=ls(u);
        else if(k==Tr[ls(u)].siz+1) return Tr[u].id;
        else k-=Tr[ls(u)].siz+1,u=rs(u);
    }
}
char opt[2];
int main()
{
    // freopen("fhq-treap.in","r",stdin);
    // freopen("fhq-treap.out","w",stdout);
    read(N,M);
    init(N);
    for(int i=1,x;i<=N;++i)
    {
        read(x);rt[i]=newNode(x,i);
    }
    for(int i=1,u,v;i<=M;++i)
    {
        read(u,v);mergeSet(u,v);
    }
    read(Q);
    for(int u,v;Q--;)
    {
        scanf("%s",opt+1);read(u,v);
        if(opt[1]=='Q')
        {
            u=getFa(u);
            if(Tr[rt[u]].siz<v)
            {
                puts("-1");
                continue;
            }
            write(kth(rt[u],v)),puts("");
        }
        else mergeSet(u,v);
    }
    return 0;
}
/*
5 1
4 3 2 5 1
1 2
7
Q 3 2
Q 2 1
B 2 3
B 1 5
Q 2 1
Q 2 4
Q 2 3
*/

并查集 + 线段树合并

考虑到没有断边操作，所以不需要去用 $\text{Link/Cut Tree}$ 这样高级的数据结构来维护，势能分析一波，发现就是一个合并，并且是查询区间 $k$ 小值，考虑主席树。

但主席树不能合并，所以考虑线段树合并，每次加边时用并查集维护并合并区间，查询即可。

AC Code 
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
const int MAXN=5e5+10;
int N,M,Q,Idx;
int Rt[MAXN],Dsu[MAXN],Id[MAXN];
struct ST
{
    int lc,rc,val;
}Tr[MAXN<<5];
void modifyX(int &p,int l,int r,int x)
{
    if(!p) p=++Idx;
    ++Tr[p].val;
    if(l==r) return ;
    int mid=(l+r)>>1;
    if(x<=mid) modifyX(Tr[p].lc,l,mid,x);
    else modifyX(Tr[p].rc,mid+1,r,x);
}
int merge(int p1,int p2,int l,int r)
{
    if((!p1)||(!p2)) return p1|p2;
    Tr[p1].val+=Tr[p2].val;
    if(l==r) return p1;
    int mid=(l+r)>>1;
    Tr[p1].lc=merge(Tr[p1].lc,Tr[p2].lc,l,mid),
    Tr[p1].rc=merge(Tr[p1].rc,Tr[p2].rc,mid+1,r);
    return p1;
}
int getFa(int x)
{
    return Dsu[x]==x?x:Dsu[x]=getFa(Dsu[x]);
}
int queryKth(int p,int l,int r,int k)
{
    if(l==r) return l;
    if(k>Tr[p].val) return 0;
    int mid=(l+r)>>1;
    if(Tr[Tr[p].lc].val>=k) return queryKth(Tr[p].lc,l,mid,k);
    else return queryKth(Tr[p].rc,mid+1,r,k-Tr[Tr[p].lc].val);
}
char opt[5];
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(N,M);
    for(int i=1,x;i<=N;++i) read(x),modifyX(Rt[i],1,N,x),Dsu[i]=i,Id[x]=i;
    Id[0]=-1;
    for(int i=1,u,v;i<=M;++i)
    {
        read(u,v);
        if(getFa(u)!=getFa(v))
        {
            int fu=getFa(u),fv=getFa(v);
            Rt[fu]=merge(Rt[fu],Rt[fv],1,N);
            Dsu[fv]=fu;
        }
    }
    read(Q);
    for(int qd,qk;Q--;)
    {
        scanf("%s",opt+1),read(qd,qk);
        if(opt[1]=='B')
        {
            if(getFa(qd)!=getFa(qk))
            {
                int fu=getFa(qd),fv=getFa(qk);
                Rt[fu]=merge(Rt[fu],Rt[fv],1,N);
                Dsu[fv]=fu;    
            }
        }
        else write(Id[queryKth(Rt[getFa(qd)],1,N,qk)],'\n');
    }
    return 0;
}
/*
5 1
4 3 2 5 1
1 2
7
Q 3 2
Q 2 1
B 2 3
B 1 5
Q 2 1
Q 2 4
Q 2 3
*/

两种方法的时间差异不大。

相关文章