「SDOI2013」森林-主席树+LCA+启发式合并

发表于 | 更新于 | 分类于 | | 阅读次数：
本文字数： 4.8k | 阅读时长 ≈ 9 分钟

小Z有一片森林，含有$N$个节点，每个节点上都有一个非负整数作为权值。初始的时候，森林中有$M$条边。

小Z希望执行$T$个操作，操作有两类：

  • Q x y k查询点$x$到点$y$路径上所有的权值中，第$k$小的权值是多少。此操作保证点$x$和点$y$连通，同时这两个节点的路径上至少有$k$个点。

  • L x y在点$x$和点$y$之间连接一条边。保证完成此操作后，仍然是一片森林。

强制在线。

对于所有的数据$n,m,T \leq 8 \times 10^4$。

链接

Luogu P3302

题解

恶心的大数据结构。

对于合并操作，我们会想到LCT，而对于查询路径上的第$k$大，又让我们想到主席树。

只能牺牲一种操作。注意到这里没有cut，所以我们可以通过启发式合并的方式，减少一个$\log$。

用并查集维护森林的大小，每次合并的时候强势暴力dfs修改树上路径主席树，以及求lca的倍增数组即可。

然后就是常规操作了。

需要用离散化，这里用了$map$。

代码

点击切换显示状态
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include <cstdio>
#include <map>
#include <cctype>
#include <algorithm>
using namespace std;

namespace fast_io {
    //...
}using namespace fast_io;

const int MAXN = 81000,maxb = 20,logn = 500;

namespace prSegTree{
    int sumn[MAXN*logn],ls[MAXN*logn],rs[MAXN*logn],cnt = 1;
    #define mid ((l+r)>>1)
    void insert(int &nown,int pre,int l,int r,int pos,int d){
        nown = ++cnt;ls[nown] = ls[pre],rs[nown] = rs[pre];
        sumn[nown] = sumn[pre] + d;
        if(l == r) return;
        else{
            if(pos <= mid) insert(ls[nown],ls[pre],l,mid,pos,d);
            if(mid+1 <= pos) insert(rs[nown],rs[pre],mid+1,r,pos,d);
        }
    }
    int query(int x1,int x2,int y1,int y2,int l,int r,int k){
        if(l == r) return l;
        else{
            int sum = sumn[ls[x1]] + sumn[ls[x2]] - sumn[ls[y1]] - sumn[ls[y2]];
            if(k <= sum) return query(ls[x1],ls[x2],ls[y1],ls[y2],l,mid,k);
            if(sum+1 <= k) return query(rs[x1],rs[x2],rs[y1],rs[y2],mid+1,r,k-sum);
        }
    }
    void build(int &nown,int l,int r){
        nown = ++cnt;
        if(l == r) return;
        else{
            build(ls[nown],l,mid);
            build(rs[nown],mid+1,r);
        }
    }
}

int fir[MAXN];
int to[MAXN*2],nex[MAXN*2],ecnt = 1;

int n,m,q,num[MAXN],last[MAXN],tot = 0;
int rt[MAXN];
int f[MAXN][maxb],dep[MAXN];
map<int,int> S;

void addedge(int u,int v){
    to[ecnt] = v,nex[ecnt] = fir[u],fir[u] = ecnt++;
    to[ecnt] = u,nex[ecnt] = fir[v],fir[v] = ecnt++;
}

namespace BCJ{
    int f[MAXN],siz[MAXN];
    int find(int x){
        return f[x]==x?x:find(f[x]);
    }
    int query(int x){
        return siz[find(x)];
    }
    void un(int x,int y){
        //y->x
        int xx = find(x),yy = find(y);
        f[yy] = xx;siz[xx] += siz[yy];
    }
    void init(){
        for(int i = 1;i<=n;i++)
            f[i] = i,siz[i] = 1;
    }
}

void pre_dfs(int nown,int fa,int depth){
    prSegTree::insert(rt[nown],rt[fa],1,tot,S[num[nown]],1);
    dep[nown] = depth;
    f[nown][0] = fa;
    for(int j = 1;j<maxb;j++)
        f[nown][j] = f[ f[nown][j-1] ][j-1];
    for(int i = fir[nown];i;i=nex[i]){
        int v = to[i];
        if(v == fa) continue;
        pre_dfs(v,nown,depth+1);
    }
}

int lca(int u,int v){
    if(dep[u] < dep[v]) swap(u,v);
    for(int j = maxb-1;j>=0;j--)
        if(dep[f[u][j]] >= dep[v])
            u = f[u][j];
    if(u == v) return u;
    for(int j = maxb-1;j>=0;j--)
        if(f[u][j] != f[v][j])
            u = f[u][j],v = f[v][j];
    return f[u][0]; 
}

void init(){
    int T;
    read(T);
    read(n),read(m),read(q);
    BCJ::init();
    for(int i = 1;i<=n;i++){
        read(num[i]);
        S[num[i]] = 0;
    }
    for(map<int,int>::iterator it = S.begin();it!=S.end();it++){
        it->second = ++tot;last[tot] = it->first;
    }
    int a,b;
    for(int i = 1;i<=m;i++){
        read(a),read(b);
        addedge(a,b);
        BCJ::un(a,b);
    }
}

void build(){
    for(int i = 1;i<=n;i++){
        if(BCJ::find(i)==i)
            pre_dfs(i,0,1);
    }
}

void link(int u,int v){
    addedge(u,v);
    if(BCJ::query(u) < BCJ::query(v)) swap(u,v);
    pre_dfs(v,u,dep[u]+1);
    BCJ::un(u,v);
}

int query(int u,int v,int k){
    int l = lca(u,v),fl = f[l][0];
    int ans = prSegTree::query(rt[u],rt[v],rt[l],rt[fl],1,tot,k);
    //printf("query: u:%d v:%d l:%d fl:%d k:%d ANS:%d\n",u,v,l,fl,k,ans);
    return last[ans];
}

void solve(){
    char op[10];int a,b,k,last = 0;
    for(int i = 1;i<=q;i++){
        read(op);read(a),read(b);
        a^=last,b^=last;
        if(op[0] == 'L')
            link(a,b);
        else if(op[0] == 'Q')
            read(k),k^=last,print(last = query(a,b,k)),print('\n');
    }
}

int main(){
    init();
    build();
    solve();
    flush();
    return 0;
}