luoguP3302 [SDOI2013]森林

https://www.luogu.org/problemnew/show/P3302

看到查询第 k 小，而且是一颗树，可以联想到在树上的主席树，a 和 b 路径中第 k 小可以通过在 a, b, lca(a, b), fa[lca(a, b)] 四个节点对应的主席树上二分得到

实现主席树是很简单的，连接两个点可以启发式合并，现在最大的问题是连接两个点后还要高效的求出 LCA，一种做法是启发式合并的时候重构倍增数组，也有一种用 LCT 维护 LCA 的方法，相对简单。博主的实现是后者

需要注意的就是找到 fa[lca(a, b)] 的时候，可以模仿 LCT findroot 函数的实现，先 access(lca)，然后 splay(lca)，找到深度次大的点即可。link 之后 root 会变，进行新操作的时候要 makeroot，才能求出正确的 LCA

总而言之，需要注意的细节还是很多的，具体还是看代码实现吧

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

typedef long long ll;

template <typename _T>

inline void read(_T &f) {

    f = 0; _T fu = 1; char c = getchar();

    while(c < '0' || c > '9') {if(c == '-') fu = -1; c = getchar();}

    while(c >= '0' && c <= '9') {f = (f << 3) + (f << 1) + (c & 15); c = getchar();}

    f *= fu;

}

const int N = 80000 + 10;

int fa[N], ch[N][2], rev[N], st[N], len;

int n, m, t;

int isroot(int u) {return ch[fa[u]][0] != u && ch[fa[u]][1] != u;}

int get(int u) {return ch[fa[u]][1] == u;}

void pushdown(int u) {

    if(rev[u]) {

        swap(ch[u][0], ch[u][1]);

        rev[ch[u][0]] ^= 1;

        rev[ch[u][1]] ^= 1;

        rev[u] ^= 1;

    }

}

void rotate(int u) {

    int old = fa[u], oldd = fa[old], k = get(u);

    if(!isroot(old)) ch[oldd][get(old)] = u; fa[u] = oldd;

    fa[ch[u][k ^ 1]] = old; ch[old][k] = ch[u][k ^ 1];

    fa[old] = u; ch[u][k ^ 1] = old;

}

void splay(int u) {

    st[len = 1] = u;

    for(int i = u; !isroot(i); i = fa[i]) st[++len] = fa[i];

    for(int i = len; i >= 1; i--) pushdown(st[i]);

    for(; !isroot(u); rotate(u)) if(!isroot(fa[u])) rotate(get(u) == get(fa[u]) ? fa[u] : u);

}

int access(int u) {

    int tmp;

    for(int i = 0; u; i = u, u = fa[u]) {

        splay(u);

        ch[u][1] = i;

        tmp = u;

    }

    return tmp;

}

void makeroot(int u) {

    access(u);

    splay(u);

    rev[u] ^= 1;

}

void link(int x, int y) {

    makeroot(x);

    fa[x] = y;

}

int LCA(int x, int y) {

    access(x);

    return access(y);

}

int rt[N], val[N * 600], lc[N * 600], rc[N * 600], a[N], b[N];

int tot = 0;

void build(int &u, int l, int r) {

    u = ++tot;

    if(l == r) return;

    int mid = (l + r) >> 1;

    build(lc[u], l, mid);

    build(rc[u], mid + 1, r);

}

void ins(int &u, int pre, int l, int r, int x) {

    u = ++tot;

    val[u] = val[pre] + 1, lc[u] = lc[pre], rc[u] = rc[pre];

    if(l == r) return;

    int mid = (l + r) >> 1;

    if(mid >= x) ins(lc[u], lc[pre], l, mid, x);

    else ins(rc[u], rc[pre], mid + 1, r, x);

}

int query(int a, int b, int c, int d, int l, int r, int k) {

    if(l == r) return l;

    int lsum = val[lc[a]] + val[lc[b]] - val[lc[c]] - val[lc[d]];

    int rsum = val[rc[a]] + val[rc[b]] - val[rc[c]] - val[rc[d]];

    int mid = (l + r) >> 1;

    if(lsum >= k) return query(lc[a], lc[b], lc[c], lc[d], l, mid, k);

    else return query(rc[a], rc[b], rc[c], rc[d], mid + 1, r, k - lsum);

}

int blen;

vector <int> g[N];

int siz[N], head[N];

int f[N]; int find(int x) {return f[x] == x ? x : f[x] = find(f[x]);}

inline void addedge(int u, int v) {

    g[u].push_back(v);

    g[v].push_back(u);

}

void dfs1(int u, int f) {

    ins(rt[u], rt[f], 1, blen, a[u]);

    for(vector <int> :: iterator it = g[u].begin(); it != g[u].end(); it++) {

        int v = *it; if(v == f) continue; dfs1(v, u);

    }

}

void Merge(int a, int b) {

    int x = find(a), y = find(b);

    if(siz[x] < siz[y]) swap(a, b), swap(x, y);

    siz[x] += siz[y]; addedge(a, b);

    link(a, b); f[y] = x;

    dfs1(b, a);

}

int lastans = 0;

int main() {

    cin >> n;

    cin >> n >> m >> t;

    for(int i = 1; i <= n; i++) {

        scanf("%d", &a[i]);

        b[i] = a[i];

        f[i] = i; siz[i] = 1;

    }

    sort(b + 1, b + n + 1);

    blen = unique(b + 1, b + n + 1) - b - 1;

    for(int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + blen + 1, a[i]) - b;

    build(rt[0], 1, blen);

    for(int i = 1; i <= n; i++) {

        ins(rt[i], rt[0], 1, blen, a[i]);

    }

    for(int i = 1; i <= m; i++) {

        int A, B;

        scanf("%d %d", &A, &B);

        Merge(A, B);

    }

    for(int i = 1; i <= t; i++) {

        char c = getchar();

        while(c != 'Q' && c != 'L') c = getchar();

        if(c == 'L') {

            int A, B;

            scanf("%d %d", &A, &B);

            A ^= lastans; B ^= lastans;

            Merge(A, B);

        } else {

            int A, B, K;

            scanf("%d %d %d", &A, &B, &K);

            A ^= lastans; B ^= lastans; K ^= lastans;

            makeroot(find(A));

            int lca = LCA(A, B), father;

            if(find(A) == lca) father = 0;

            else {

                access(lca); splay(lca);

                father = ch[lca][0];

                while(ch[father][1]) {

					father = ch[father][1];

					pushdown(father);

				}

            }

            printf("%d\n", lastans = b[query(rt[A], rt[B], rt[lca], rt[father], 1, blen, K)]);

        }

    }

    return 0;

}

巴特西

luoguP3302 [SDOI2013]森林

最新文章

热门文章