gayyyy

Problem

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

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

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

强制在线

Solution

启发式合并

倍增处理 lca

卡卡空间

然后就行辣

复习下板子

Code

// Code by ajcxsu
// Problem: forest

#include<bits/stdc++.h>
#define CLR(x) memset(x, 0, sizeof(x))
using namespace std;

template<typename T> inline void gn(T &x) {
    char ch=getchar(), pl=0;
    x=0;
    while(ch<'0' || ch>'9') pl=(ch=='-'), ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
    x*=pl?-1:1;
}
inline void gc(char &c) {
    c=getchar();
    while(!isalpha(c)) c=getchar();
}

const int N=8e4+10, M=2.1105e7, MM=2e5+10, OP=18;
int h[N], to[MM], nexp[MM], p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }
int siz[N], dep[N];

/* chairman tree */
struct Node *nil;
struct Node {
    Node *ls, *rs;
    int v;
    Node(int val=0):v(val) { ls=rs=nil; }
} *nd[N], po[M], *pp=po;

void updata(Node *&x, int l, int r, int d) {
    Node *nd=pp++;
    *nd=*x, x=nd, x->v++;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(d<=mid) updata(x->ls, l, mid, d);
    else updata(x->rs, mid+1, r, d);
}

int query(Node *a, Node *b, Node *c, Node *d, int l, int r, int k) {
    if(l==r) return l;
    int v=a->ls->v+b->ls->v-c->ls->v-d->ls->v, mid=(l+r)>>1;
    if(k<=v) return query(a->ls, b->ls, c->ls, d->ls, l, mid, k);
    else return query(a->rs, b->rs, c->rs, d->rs, mid+1, r, k-v);
}

/* lca */
int gup[N][OP];
int lca(int s, int t) {
    if(dep[s]<dep[t]) swap(s, t);
    for(int j=OP-1;j>=0;j--)
        if(dep[gup[s][j]]>=dep[t]) s=gup[s][j];
    if(s!=t) {
        for(int j=OP-1;j>=0;j--)
            if(gup[s][j]!=gup[t][j]) s=gup[s][j], t=gup[t][j];
        s=gup[s][0];
    }
    return s;
}

/* Union */
int n, m, t, k;
int lis[N], arr[N];
void dfs(int x, int fa) {
    dep[x]=dep[fa]+1, gup[x][0]=fa, nd[x]=nd[fa], updata(nd[x], 1, k, arr[x]);
    for(int j=1;j<OP;j++) gup[x][j]=gup[gup[x][j-1]][j-1];
    for(int u=h[x];u;u=nexp[u])
        if(to[u]!=fa) dfs(to[u], x);
}

/* UF */
int fa[N];
int Find(int x) { return fa[x]?fa[x]=Find(fa[x]):x; }
bool Union(int a, int b) {
    int af=Find(a), bf=Find(b);
    if(af==bf) return false;
    if(siz[af]>siz[bf]) swap(af, bf), swap(a, b);
    dfs(a, b);
    fa[af]=bf, siz[bf]+=siz[af];
    return true;
}

map<int, int> mp;
/* init */
void ini() {
    pp=po, nil=pp++, *nil=Node(), nil->ls=nil->rs=nil;
    fill(nd, nd+N, nil);
    fill(siz+1, siz+1+n, 1), fill(dep+1, dep+1+n, 1);
}

int main() {
    ios::sync_with_stdio(false);
    gn(n), gn(n), gn(m), gn(t);
    ini();
    int lst=0;
    for(int i=1;i<=n;i++) gn(arr[i]), lis[i]=arr[i];
    sort(lis+1, lis+1+n), k=unique(lis+1, lis+1+n)-lis-1;
    for(int i=1;i<=k;i++) mp[lis[i]]=i;
    for(int i=1;i<=n;i++) arr[i]=mp[arr[i]], updata(nd[i], 1, k, arr[i]);
    int u, v;
    for(int i=1;i<=m;i++) gn(u), gn(v), ins(u, v), ins(v, u), Union(u, v);
    char con;
    int a, b, c;
    while(t--) {
        gc(con), gn(a), gn(b), a^=lst, b^=lst;
        if(con=='Q') {
            gn(c), c^=lst;
            int l=lca(a, b), lf=gup[l][0];
            printf("%d\n", lst=lis[query(nd[a], nd[b], nd[l], nd[lf], 1, k, c)]);
        }
        else if(con=='L') ins(a, b), ins(b, a), Union(a, b);
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-3302.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆