线段树合并

权值线段树

一般的线段树维护的是区间上的信息，比如区间最大值，最小值，区间和等，维护的区间都对应数组的一段连续的下标。

而权值线段树于此不同。权值线段树是指以值域为区间的线段树，它维护的区间是一段值域，所以称之为权值线段树。

动态开点

因为权值线段树维护的是值域，而值域的范围可能很大，且值域中的许多位置是空的。我们可以省去这些空间，只将需要用的点表示出来即可。此时，叶节点的数量就是元素的数量。若元素值个数为$n$，值域为$m$，则每个叶节点的祖先最多$logm$个，所以这棵树的节点数量也不会超过$nlogm$个。

线段树合并

线段树合并指将多棵线段树上的信息合并到一棵线段树上。每次合并两棵，合并后的信息就在其中一棵线段树上。

对于每次合并，我们从根节点往下依次遍历每个位置，如果某个位置两棵树都存在节点，则将一棵树上的信息加到另一棵树上，然后继续处理它们的左儿子和右儿子。如果某个位置只有一棵树有节点或者两棵树都没有节点，则只需处理当前位置，不需要再往下合并了。

code

void merge(int &r1,int r2,int l,int r){
    if(!r1||!r2){
        r1=r1+r2;return;
    }
    if(l==r){
        s[r1]+=s[r2];return;
    }
    int mid=(l+r)/2;
    merge(tr[r1].lc,tr[r2].lc,l,mid);
    merge(tr[r1].rc,tr[r2].rc,mid+1,r);
    s[r1]=s[tr[r1].lc]+s[tr[r1].rc];
}
1
2
3
4
5
6
7
8
9
10
11
12

例题

【HNOI2012】永无乡

这道题需要用到并查集和线段树合并。

开始时对每一座岛建立一棵线段树，第$i$个叶节点为一表示重要程度为$i$的岛与这个岛连通。维护区间叶节点数量$s$，$rt[i]$表示节点$i$的权值线段树的根，然后对$M$条边进行合并。比如对于边$(a,b)$，如果$a,b$不在一个连通块，则设$x=find(a),y=find(b)$，将$x$的线段树和$y$的线段树进行合并，然后$fa[y]=x$，表示将$y$的线段树合并到$x$的线段树中。

对于$B$操作，同上，并查集处理即可。对于$Q$操作，查找$x$的线段树，找到第$k$小的叶节点即可。

code

#include
using namespace std;
int n,m,q,tot=0,x,y,c[100005],re[100005],rt[100005],fa[100005],s[5000005];
char ch;
struct node{
    int lc,rc;
}tr[5000005];
int find(int ff){
    if(fa[ff]!=ff) fa[ff]=find(fa[ff]);
    return fa[ff];
}
void pt(int &k,int l,int r,int v){
    if(!k) k=++tot;
    if(l==r&&l==v){
        ++s[k];return;
    }
    if(l>v||r<v) return;
    if(l==r) return;
    int mid=(l+r)/2;
    if(v<=mid) pt(tr[k].lc,l,mid,v);
    else pt(tr[k].rc,mid+1,r,v);
    s[k]=s[tr[k].lc]+s[tr[k].rc];
}
void merge(int &r1,int r2,int l,int r){
    if(!r1||!r2){
        r1=r1+r2;return;
    }
    if(l==r){
        s[r1]+=s[r2];return;
    }
    int mid=(l+r)/2;
    merge(tr[r1].lc,tr[r2].lc,l,mid);
    merge(tr[r1].rc,tr[r2].rc,mid+1,r);
    s[r1]=s[tr[r1].lc]+s[tr[r1].rc];
}
void gt(int x,int y){
    int x1=find(x),x2=find(y);
    if(x1==x2) return;
    merge(rt[x1],rt[x2],1,n);
    fa[x2]=x1;
}
int find(int k,int l,int r,int v){
    if(!k) return -1;
    if(l==r){
        if(v==1) return re[l];
        return -1;
    }
    int mid=(l+r)/2;
    if(v<=s[tr[k].lc]&&tr[k].lc) return find(tr[k].lc,l,mid,v);
    return find(tr[k].rc,mid+1,r,v-s[tr[k].lc]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&c[i]);
        re[c[i]]=i;fa[i]=i;
        pt(rt[i],1,n,c[i]);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        gt(x,y);
    }
    scanf("%d",&q);
    while(q--){
        ch=getchar();
        while(ch!='B'&&ch!='Q') ch=getchar();
        scanf("%d%d",&x,&y);
        if(ch=='B'){
            gt(x,y);
        }
        else{
            x=find(x);
            printf("%d\n",find(rt[x],1,n,y));
        }
    }
    return 0;
}
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