数据结构 Trick 之:子树 k 距离内问题

· · 算法·理论

能够解决的题目类型

这个 Trick 能解决的题目形如:

那么——二维,启动!

我们把一个数点 x 变成二维平面上的点:(depp_x\,,dfn_x)。 那么对于一个点 p 的询问就变成了横坐标在 [depp_p\,,depp_p+k] 中,纵坐标在 [dfn_p\,,dfn_p+sz_p-1] 的点的极值/排名/和。

这个显然可以用树套树,但是 O(n\,log^2\,n),有没有更优的方法呢?

我们考虑主席树,但是 主席树必须满足可减性,而最值没有。 但是,当一个点的横坐标在属于 [1,depp_p-1] 时,他的纵坐标一定不属于 [depp_p\,,dep_p+k],也就是说我们并不需要将两颗线段树相减,那么询问也就不用讲满足可减性。

所以我们就可以愉快地切题了。

算法流程

  1. 用一个 dfs 求出每个节点的 dfn,sz,depp
  2. 把节点按照深度排序,一个一个加入主席树,并记录对于每个深度的最后一课主席树的根的下标 idx

例题代码

本 Trick 的代码基本每道题没什么变化,直接套用就行了 CF893F Subtree Minimum Query

#include <bits/stdc++.h>
using namespace std;

#define midd ((node[u].l + node[u].r) >> 1)
constexpr int maxn = 100010;

int n, r, m, v[maxn], a, b, dfn[maxn], nowdfn, depp[maxn], s[maxn], idx[maxn], sz[maxn], lans, maxdep = 0;
vector <int> G[maxn];

struct nodee {
    int v, l, r, ls, rs;
} ;
struct tr {
    nodee node[maxn << 5];
    int root[maxn], cnt;
    void build(int &u, int l, int r) {
        u = ++cnt;
        node[u] = {1000000000, l, r, 0, 0};
        if (l == r) return ;
        build(node[u].ls, l, midd);
        build(node[u].rs, midd + 1, r);
        return ;
    }
    void update(int &u, int pree, int x, int k) {
        u = ++cnt;
        node[u] = node[pree];
        node[u].v = min(node[u].v, k);
        if (node[u].l == node[u].r) return ;
        if (x <= midd) update(node[u].ls, node[pree].ls, x, k);
        else update(node[u].rs, node[pree].rs, x, k);
        return ;
    }
    int query(int u, int l, int r) {
        if (node[u].l >= l && node[u].r <= r) return node[u].v;
        int ress = 1000000000;
        if (l <= midd) ress = min(query(node[u].ls, l, r), ress);
        if (r > midd) ress = min(query(node[u].rs, l, r), ress);
        return ress;
    }
} t;

void dfs(int u, int fa) {
    sz[u] = 1;
    dfn[u] = ++nowdfn;
    for (int now : G[u]) {
        if (now == fa) continue;
        depp[now] = depp[u] + 1;
        maxdep = max(maxdep, depp[now]);
        dfs(now, u);
        sz[u] += sz[now];
    }
    return ;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    cin >> n >> r;
    depp[r] = 1;
    for (int i = 1; i <= n; i++) {
        s[i] = i;
        cin >> v[i];
    }
    for (int i = 1; i < n; i++) {
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(r, 0);
    sort(s + 1, s + 1 + n, [](int a, int b){return depp[a] < depp[b];});
    // 以上为第一部分 dfs
    t.build(t.root[0], 1, n);
    idx[0] = t.root[0];
    for (int i = 1; i <= n; i++) {
        t.update(t.root[i], t.root[i - 1], dfn[s[i]], v[s[i]]);
        if (depp[s[i]] != depp[s[i + 1]]) idx[depp[s[i]]] = i;
    }
    // 以上为第二部分 主席树预处理
    cin >> m;
    while (m--) {
        cin >> a >> b;
        a = (a + lans) % n + 1;
        b = (b + lans) % n;
        lans = t.query(t.root[idx[min(maxdep, depp[a] + b)]], dfn[a], dfn[a] + sz[a] - 1);
        cout << lans << '\n';
    }

    return 0;
}