[BZOJ 3123] [SDOI 2013]森林(可持久化线段树+启发式合并)

题面

给出一个n个节点m条边的森林，每个节点都有一个权值。有两种操作：

1. Q x y k查询点x到点y路径上所有的权值中，第k小的权值是多少。此操作保证点x和点y连通，同时这两个节点的路径上至少有k个点。
   
2. L x y在点x和点y之间连接一条边。保证完成此操作后，仍然是一片森林。

分析

用并查集维护连通性以及每个联通块的大小

用主席树维护路径上第k大，第x棵主席树维护的是节点x到根的链上权值的出现情况，类似[BZOJ2588]Count on a tree(LCA+主席树)。不过这道题不用dfs序，直接根据编号建树。

合并x,y的时候启发式合并。若x子树大小比y小，就重新dfs一遍x的子树，并把y到根的链上权值加进去。反之同理。详情见代码。时间复杂度\(O(n \log ^2n)\)

代码

#include<iostream>
#include<cstdio>
#include<cstring> 
#include<algorithm>
#include<cmath>
#include<vector>
#define INF 0x3f3f3f3f
#define maxn 100000
#define maxlogn 22
#define maxnlogn 10000000
using namespace std;
inline void qread(int &x){
    x=0;
    int sign=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') sign=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    x=x*sign;
}
inline void qprint(int x){
    if(x<0){
        putchar('-');
        qprint(-x);
    }else if(x==0){
        putchar('0');
        return; 
    }else{
        if(x>=10) qprint(x/10);
        putchar('0'+x%10);
    }
}

int testcase;//是测试点编号，不是数据组数... 
int n,m,q,mv;
int val[maxn+5];
int tmp[maxn+5];
int discrete(int *a,int n){
    int sz=0;
    for(int i=1;i<=n;i++) tmp[i]=a[i];
    sort(tmp+1,tmp+1+n);
    sz=unique(tmp+1,tmp+1+n)-tmp-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(tmp+1,tmp+1+sz,a[i])-tmp;
    }
    return sz;
}

struct edge{
    int from;
    int to;
    int next;
}E[maxn*2+5];
int head[maxn+5];
int esz;
void add_edge(int u,int v){
    esz++;
    E[esz].from=u;
    E[esz].to=v;
    E[esz].next=head[u];
    head[u]=esz;
    esz++;
    E[esz].from=v;
    E[esz].to=u;
    E[esz].next=head[v];
    head[v]=esz;
}

struct disjoint_set{
    int fa[maxn+5];
    int sz[maxn+5];
    void ini(int n){
        for(int i=1;i<=n;i++){
            fa[i]=i;
            sz[i]=1;
        }
    }
    int find(int x){
        if(fa[x]==x) return x;
        else return fa[x]=find(fa[x]);
    }
    inline int size(int x){//返回x所在联通块大小 
        return sz[find(x)];
    }
    void merge(int x,int y){
        int fx=find(x),fy=find(y);
        if(sz[fx]>sz[fy]) swap(fx,fy);
        fa[fx]=fy;
        sz[fy]+=sz[fx]; 
    } 
}S;

struct persist_segment_tree{
#define lson(x) (tree[x].ls)
#define rson(x) (tree[x].rs)
    struct node{
        int ls;
        int rs;
        int val;
    }tree[maxnlogn+5];
    int ptr;
    inline void push_up(int x){
        tree[x].val=tree[lson(x)].val+tree[rson(x)].val;
    } 
    void update(int &x,int last,int upos,int l,int r){
        x=++ptr;
        tree[x]=tree[last];
        if(l==r){
            tree[x].val++;
            return;
        }
        int mid=(l+r)>>1;
        if(upos<=mid) update(lson(x),lson(last),upos,l,mid);
        else update(rson(x),rson(last),upos,mid+1,r);
        push_up(x);
    }
    int query(int x,int y,int lc,int lcfa,int k,int l,int r){
        if(l==r){
            return l;
        }
        int mid=(l+r)>>1;
        int lcnt=tree[lson(x)].val+tree[lson(y)].val-tree[lson(lc)].val-tree[lson(lcfa)].val;
        if(k<=lcnt) return query(lson(x),lson(y),lson(lc),lson(lcfa),k,l,mid);
        else return query(rson(x),rson(y),rson(lc),rson(lcfa),k-lcnt,mid+1,r); 
    }
#undef lson
#undef rson
}T;
int root[maxn+5];

int log2n;
int deep[maxn+5];
int anc[maxn+5][maxlogn+5];
void dfs(int x,int fa){
    deep[x]=deep[fa]+1;
    anc[x][0]=fa;
    for(int i=1;i<=log2n;i++) anc[x][i]=anc[anc[x][i-1]][i-1];
    T.update(root[x],root[fa],val[x],1,mv);
    for(int i=head[x];i;i=E[i].next){
        int y=E[i].to;
        if(y!=fa){
            dfs(y,x);
        }
    } 
}
int lca(int x,int y){
    if(deep[x]<deep[y]) swap(x,y);
    for(int i=log2n;i>=0;i--){
        if(deep[anc[x][i]]>=deep[y]) x=anc[x][i];
    }
    if(x==y) return x;
    for(int i=log2n;i>=0;i--){
        if(anc[x][i]!=anc[y][i]){
            x=anc[x][i];
            y=anc[y][i];
        }
    }
    return anc[x][0];
}

void merge(int x,int y){
    if(S.size(x)>S.size(y)) swap(x,y);
    S.merge(x,y);
    add_edge(x,y);
    if(deep[y]==0) deep[y]=1;
    dfs(x,y);//注意不是dfs(x,0),因为x的父亲是y 
} 
int query(int x,int y,int k){
    int lc=lca(x,y);
    int id=T.query(root[x],root[y],root[lc],root[anc[lc][0]],k,1,mv);
    return tmp[id];
}


int main(){
//  freopen("5.in","r",stdin);
    int last=0;
    char op[2];
    int x,y,k;
    qread(testcase);
    qread(n);
    qread(m);
    qread(q);
    S.ini(n);
    log2n=log2(n)+1; 
    for(int i=1;i<=n;i++) qread(val[i]);
    mv=discrete(val,n);
    for(int i=1;i<=m;i++){
        qread(x);
        qread(y);
        add_edge(x,y);
        S.merge(x,y);
    } 
    for(int i=1;i<=n;i++){
        if(!anc[i][0]) dfs(i,0);
    }
    for(int i=1;i<=q;i++){
        scanf("%s",op);
        if(op[0]=='Q'){
            qread(x);
            qread(y);
            qread(k);
            x^=last;
            y^=last;
            k^=last;
            last=query(x,y,k);
            qprint(last);
            putchar('\n'); 
        }else{
            qread(x);
            qread(y);
            x^=last;
            y^=last;
            merge(x,y);
        }
    }
}
/*
1
8 4 8
1 1 2 2 3 3 4 4
4 7
1 8
2 4
2 1
Q 8 7 3 
Q 3 5 1
Q 10 0 0
L 5 4
L 3 2 
L 0 7
Q 9 2 5 
Q 6 1 6
*/