P3302 森林 并查集+树上启发式合并+主席树

P3302 森林 并查集+树上启发式合并+主席树 题目思路

对于连边操作，我们使用并查集维护每一个连通块，在连边操作时对每条边连接的两个顶点做启发式合并。

对于查询操作，在主席树上做树上前缀和二分区间第 k k k大即可。

注意 l c a lca lca要求在线重建，必须跑满 l o g log log。

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e6 + 10, MOD = 1e9 + 7;
int w[N], b[N];

struct UnionFind {
    std::vector par, rank, size;
    int c;
    UnionFind() {}
    UnionFind(int n) : par(n), rank(n, 0), size(n, 1), c(n) {
        for(int i = 0; i  1, sum = tree[lc[R]] + tree[lc[L]] - tree[lc[lca_fa]] - tree[lc[lca]];
        if(sum >= kth) return query(l, mid, lc[L], lc[R], lc[lca], lc[lca_fa], kth);
        else return query(mid + 1, r, rc[L], rc[R], rc[lca], rc[lca_fa], kth - sum);
    }
}


#define root pdt::root
#define SEGRG 1, n1

int dep[N], fa[N][21], siz[N], n1, rt = 1;

bitset vis;

int get_rank(int x) { return lower_bound(b + 1, b + 1 + n1, x) - b; }

void dfs(int u, int ufa, int rt){
    dep[u] = dep[ufa] + 1, siz[rt] += 1, vis.set(u);
    fa[u][0] = ufa, uf.set_fa(u, ufa);
    for(int i = 1; i  u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    pdt::build(root[0], SEGRG);
    for(int i = 1; i > op;
        if(op == 'Q'){
            int x, y, k; cin >> x >> y >> k;
            x ^= lastans, y ^= lastans, k ^= lastans;
            //cout