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

小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$。

代码

#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;
}