洛谷P2633 Count on a tree 主席树

😊 | Powered By HeartFireY

Problem Description

给定一棵 n n n​ 个节点的树，每个点有一个权值。有 m m m​ 个询问，每次给你 u , v , k u,v,k u,v,k​ 你需要回答 u  xor last u \text{ xor last} u xor last​ 和 v v v 这两个节点间第 k k k 小的点权。

其中 last \text{last} last 是上一个询问的答案，定义其初始为 0 0 0，即第一个询问的 u u u 是明文。

Problem Analysis

动态查询树上区间点权第 k k k​小，且查询之间具有关系，因此考虑建立主席树维护区间信息。

首先回顾主席树维护线性区间第 k k k大/小时我们的处理思路：

对于全局区间第 k k k​​小时，我们建立全局权值线段树，维护的区间和表示某点子树中点的个数。那么我们在寻找区间第 k k k​小时，只需要左右二分寻找即可。而对于某个区间的第 k k k​小，一个朴素的方式便是我们每次都建立一颗线段树，但显然这样是不明智的算法。那么我们是如何查询这个区间第 k k k小的呢？

对于这个维护的过程我们很容易联想到前缀和的概念，我们可以先离线建树，对于每个点建立一棵主席树，维护 [ 1 , i ] [1, i] [1,i]区间，那么对于区间查询 [ l , r ] [l, r] [l,r]时，我们只需要查询到区间 [ 1 , l − 1 ] [1, l - 1] [1,l−1]和 [ 1 , r ] [1, r] [1,r]即可取得区间的信息，实现区间查询。

然后分析样例，作出样例所示的树(假设以 1 1 1为根节点)：

那么我们可以发现，对于树上区间查询，我们也可以利用类似于线性区间查询的思路进行解决，但是由于树的结构限制，我们把线性区间的前缀和改为树上前缀和的形式： q u e r y ( u ,   v )   =   s u m [ u ] + s u m [ v ] − s u m [ l c a ( u ,   v ) ] − s u m [ f a [ l c a ( u ,   v ) ] ] query(u,\ v)\ =\ sum[u]+sum[v]-sum[lca(u,\ v)]-sum[fa[lca(u,\ v)]] query(u, v) = sum[u]+sum[v]−sum[lca(u, v)]−sum[fa[lca(u, v)]] 下面我们来说明这个式子：

如上，从根节点到 5 5 5号节点的路径+从根节点到 7 7 7号节点的路径重复了两次，那么我们要减去重叠的信息：对于根节点到交点父节点的信息均重复两次，到交点的信息重复一次(因为交点在链上，需要保留一次信息)，因此前缀和形式便是 s u m [ u ] + s u m [ v ] − s u m [ l c a ( u ,   v ) ] − s u m [ f a [ l c a ( u ,   v ) ] ] sum[u]+sum[v]-sum[lca(u,\ v)]-sum[fa[lca(u,\ v)]] sum[u]+sum[v]−sum[lca(u, v)]−sum[fa[lca(u, v)]]​。

那么这道题便是主席树线性静态区间第 k k k小的便是题目了，只需要额外加个树剖 L C A LCA LCA即可。

Accepted Code

#include 
#define id(x) (lower_bound(b + 1, b + le + 1, a[x]) - b)
#define rid(x) (b[x])
using namespace std;

const int N = 1e5 + 10;

int n, m, le, ans = 0, lastans = 0;
int a[N], b[N], f[N][19], dep[N];
vector g[N];

struct node{ int sum, lc, rc; }tree[N  1;
    build(tree[rt.lc = ++cnt], l, mid);
    build(tree[rt.rc = ++cnt], mid + 1, r);
}

inline void update(node pre, node &rt, int l, int r, int p){
    rt.sum = pre.sum + 1;
    if(l == r) return;
    int mid = l + r >> 1;
    if(p > 1;
    if(sum >= k) return query(tree[u.lc], tree[v.lc], tree[lca.lc], tree[lca_fa.lc], l, mid, k);
    return query(tree[u.rc], tree[v.rc], tree[lca.rc], tree[lca_fa.rc], mid + 1, r, k - sum);
}

inline void dfs(int u, int fa){
    update(tree[root[fa]], tree[root[u] = ++cnt], 1, le, id(u));
    f[u][0] = fa;
    dep[u] = dep[fa] + 1;
    for(register int i = 1; i = dep[v]) u = f[u][i];
    if(u == v) return u;
    for(register int i = 18; i >= 0; i--)
        if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
    return f[u][0];
}

inline int querypath(int u, int v, int k){
    int lcaa = lca(u, v);
    return rid(query(tree[root[u]], tree[root[v]], tree[root[lcaa]], tree[root[f[lcaa][0]]], 1, le, k));
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    //freopen("stdin.in", "r", stdin);
    //freopen("stdout.out", "w", stdout);
    cin >> n >> m;
    for(register int i = 1; i > a[i]; b[i] = a[i]; }
    for(register int i = 1, u, v; i > u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }
    sort(b + 1, b + 1 + n);
    le = unique(b + 1, b + n + 1) - (b + 1);
    build(tree[root[0] = ++cnt], 1, le);
    dfs(1, 0);
    while(m--){
        int u, v, k; cin >> u >> v >> k;
        ans = querypath(u ^ lastans, v, k);
        cout