题目链接

Luogu3302

BZOJ3213

题意

给出一堆森林（每个点有权值）和两种操作：

• 在点 x 和点 y 间连一条边，保证操作后图还是森林；

• 询问点 x 与点 y 之间路径上第 k 小的权值，保证 x,y 连通且之间至少有 k 个结点。

要求：

• 强制在线。

算法分析

看到题目中的“求第 k 大”，自然就想到主席树。在树上操作主席树，可以让每个版本的主席树维护一个点到根节点路径上的信息，可以从它的父节点继承过来。每次查询 (x, y, k) 时，在 x,y,lca(x,y),fa(lca(x,y)) 四个版本上跑主席树找第 k 大即可（判断 k 与 sum(x)+sum(y)-sum(lca(x,y))-sum(fa(lca(x,y))) 的关系）。那么剩下的就是处理连边操作了。

连边可以直接用启发式合并暴力合并两棵树。用并查集维护树的大小，把小的树怼到大的树里，可以保证时间复杂度是均摊 O(logn) 的。直接 dfs 那颗较小的树，重新构建这些结点的 lca 的倍增数组、深度和主席树就行了。其中维护倍增数组和主席树的时间复杂度是 O(logn) 的，所以最终合并的复杂度是 O(log^2n) 。

注意事项

• 权值范围是 1E9 ，别忘了离散化；

• 主席树查询第 k 大走右子树时，不要忘了将 k 减去左子树的 sum 。

代码实现

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN=88000;
const int MAXB=20;
int T, n, m, q;
struct UnionFind
{
    int f[MAXN], sz[MAXN];
    void init()
    {
        for (int i=1; i<=n; i++) f[i]=i, sz[i]=1;
    }
    int getf(int x)
    {
        if (x==f[x]) return x;
        return f[x]=getf(f[x]);
    }
    void merge(int x, int y)
    {
        int xx=getf(x), yy=getf(y);
        f[xx]=yy; sz[yy]+=sz[xx]; sz[xx]=0;
    }
} uf;
struct PersistentSegmentTree
{
    struct Node
    {
        int sum, lc, rc;
    } nodes[MAXN*MAXB*MAXB];
    int root[MAXN], cnt;
    void init()
    {
        memset(nodes, 0, sizeof nodes);
        cnt=0;
    }
    void update(int& x, int y, int l, int r, int k)
    {
        x=++cnt; nodes[x]=nodes[y]; nodes[x].sum++;
        if (l==r) return;
        int mid=(l+r)>>1;
        if (k<=mid) update(nodes[x].lc, nodes[y].lc, l, mid, k);
        else update(nodes[x].rc, nodes[y].rc, mid+1, r, k);
    }
    int query(int x, int y, int z, int w, int l, int r, int k)
    {
        if (l==r) return l;
        int p=nodes[nodes[x].lc].sum+nodes[nodes[y].lc].sum
             -nodes[nodes[z].lc].sum-nodes[nodes[w].lc].sum;
        int mid=(l+r)>>1;
        if (k<=p) return query(nodes[x].lc, nodes[y].lc, nodes[z].lc, nodes[w].lc, l, mid, k);
        else return query(nodes[x].rc, nodes[y].rc, nodes[z].rc, nodes[w].rc, mid+1, r, k-p);
    }
} pst;
struct Tree
{
    int p, a[MAXN], sub[MAXN];
    int fa[MAXN][MAXB], dep[MAXN];
    vector<int> g[MAXN];
    void init()
    {
        for (int i=1; i<=n; i++) sub[i]=a[i];
        sort(sub+1, sub+n+1);
        p=unique(sub+1, sub+n+1)-sub-1;
        for (int i=1; i<=n; i++) pst.update(pst.root[i], 0, 1, p, key(a[i]));
        memset(fa, 0, sizeof fa);
        for (int i=1; i<=n; i++) dep[i]=1, g[i].clear();
    }
    int key(int k)
    {
        return lower_bound(sub+1, sub+p+1, k)-sub;
    }
    int lca(int x, int y)
    {
        if (dep[x]<dep[y]) swap(x, y);
        for (int b=MAXB-1; b>=0; b--)
            if (dep[fa[x][b]]>=dep[y]) x=fa[x][b];
        if (x==y) return x;
        for (int b=MAXB-1; b>=0; b--)
            if (fa[x][b]!=fa[y][b]) x=fa[x][b], y=fa[y][b];
        return fa[x][0];
    }
    void dfs(int x, int f, int d)
    {
        fa[x][0]=f; dep[x]=d;
        for (int b=1; b<MAXB; b++)
            fa[x][b]=fa[fa[x][b-1]][b-1];
        pst.update(pst.root[x], pst.root[f], 1, p, key(a[x]));
        for (int i=0; i<g[x].size(); i++)
        {
            int y=g[x][i];
            if (y!=f) dfs(y, x, d+1);
        }
    }
    int query(int x, int y, int k)
    {
        int z=lca(x, y);
        return sub[pst.query(pst.root[x], pst.root[y],
                   pst.root[z], pst.root[fa[z][0]], 1, p, k)];
    }
    void link(int x, int y)
    {
        if (uf.sz[uf.getf(x)]>uf.sz[uf.getf(y)]) swap(x, y);
        uf.merge(x, y);
        dfs(x, y, dep[y]+1);
        g[x].push_back(y);
        g[y].push_back(x);
    }
} tr;
int main()
{
//  freopen("P3302.in", "r", stdin);
//  freopen("P3302.out", "w", stdout);
    scanf("%d%d%d%d", &T, &n, &m, &q);
    for (int i=1; i<=n; i++) scanf("%d", &tr.a[i]);
    uf.init();
    pst.init();
    tr.init();
    for (int i=1; i<=m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        tr.link(x, y);
    }
    for (int i=1, lastans=0; i<=q; i++)
    {
        char op;
        int x, y, k;
        scanf("\n%c", &op);
        if (op=='Q')
        {
            scanf("%d%d%d", &x, &y, &k);
            x^=lastans; y^=lastans; k^=lastans;
            printf("%d\n", lastans=tr.query(x, y, k));
        }
        else
        {
            scanf("%d%d", &x, &y);
            x^=lastans; y^=lastans;
            tr.link(x, y);
        }
    }
    return 0;
}