【BZOJ 3123】【SDOI 2013】森林 / 题解

【BZOJ 3123】【SDOI 2013】森林 / 题解

BZOJ原题地址

洛谷原题地址

思路

两个操作,求路径上第k大,还要连边。
前者让我们想到主席树,后者又是典型的LCT。
但是LCT我不会啊,所以我写了一发主席树。
对于查询,LCA一下,差分即可。
对于连边,那就。。。连边吧。因为保证连边之后依然是森林,就可以启发式合并,并查集维护。
注意这道题的输入有一个很坑的地方。第一行输入testcase,用处是什么呢?真的只是标明 testcase 而不是多组数据。

代码

#include <bits/stdc++.h>
#define maxn 100010
#define maxm 40000000//注意主席树一定要开大
#define mid ((l+r)>>1)
using namespace std;
struct Edge{
    int to,next;
    Edge(int a=0,int b=0){
        to=a,next=b;
    }
}l[maxn*2];
int head[maxn],cnt,p[maxn][25],d[maxn],fa[maxn],a[maxn],INF;
int n,m,q,id,siz[maxn],L[maxm],R[maxm],tree[maxm],rt[maxn];
int find(int x){
    return fa[x]==x?fa[x]:fa[x]=find(fa[x]);
}
void Add(int a,int b){
    l[++cnt]=Edge(b,head[a]);
    head[a]=cnt;
}
void Merge(int a,int b){
    int fx=find(a),fy=find(b);
    fa[fx]=fy;siz[fy]+=siz[fx];
}
void insert(int x,int &y,int l,int r,int val){
    if (!y) y=++id;
    tree[y]=tree[x]+1;
    if (l==r) return;
    if (val<=mid) R[y]=R[x],insert(L[x],L[y],l,mid,val);
    else L[y]=L[x],insert(R[x],R[y],mid+1,r,val);
}
int query(int x,int y,int w,int e,int l,int r,int k){
    if (l==r) return l;
    int tem=tree[L[x]]+tree[L[y]]-tree[L[w]]-tree[L[e]];
    if (tem>=k) return query(L[x],L[y],L[w],L[e],l,mid,k);
    else return query(R[x],R[y],R[w],R[e],mid+1,r,k-tem);
}
void Build(int u){
    d[u]=d[p[u][0]]+1;
    for (int i=1;(1<<i)<=d[u];i++)
        p[u][i]=p[p[u][i-1]][i-1];
    rt[u]=0;
    insert(rt[p[u][0]],rt[u],0,INF,a[u]);
    for (int i=head[u];i;i=l[i].next){
        int v=l[i].to;if (v==p[u][0]) continue;
        p[v][0]=u;Build(v);
    }
}
int lca(int a,int b){
    if (d[a]<d[b]) swap(a,b);
    for (int i=24;i>=0;i--)
        if (d[p[a][i]]>=d[b]) a=p[a][i];
    if (a==b) return a;
    for (int i=24;i>=0;i--)
        if (p[a][i]!=p[b][i]) a=p[a][i],b=p[b][i];
    return p[a][0];
}
int main(){
    ios::sync_with_stdio(false);
    int t;cin>>t;
    cin>>n>>m>>q;
    for (int i=1;i<=n;i++)
        fa[i]=i,cin>>a[i],INF=max(INF,a[i]),siz[i]=1;
    for (int i=1,t1,t2;i<=m;i++){
        cin>>t1>>t2;Add(t1,t2);
        Add(t2,t1);Merge(t1,t2);
    }
    for (int i=1;i<=n;i++)
        if (!p[i][0]) Build(i);
    int ans=0,x,y,k;char op;
    for (int i=1;i<=q;i++){
        cin>>op;if (op=='Q'){
            cin>>x>>y>>k;
            x^=ans,y^=ans,k^=ans;int lc=lca(x,y);
            ans=query(rt[x],rt[y],rt[lc],rt[p[lc][0]],0,INF,k);
            cout<<ans<<endl;
        }else{
            cin>>x>>y;x^=ans,y^=ans;
            int fx=find(x),fy=find(y);
            if (siz[fx]>siz[fy]) swap(x,y);
            Add(x,y);Add(y,x);Merge(x,y);
            p[x][0]=y;Build(x);
        }
    }
    return 0;
}
Show Comments