893F - Subtree Minimum Query

题意

给出一棵树，每次询问 \(x\) \(k\)，求以 \(x\) 为根结点的子树中的结点到结点 \(x\) 的距离小于等于 \(k\) 的结点权值最小值。

分析

可持久化线段树，对每个结点都建树，然后尽可能复用子孙结点的线段树。

对于一般的线段树，我们并不需要记录左右子结点的标号，因为如果当前节点标号为 \(rt\) ，则左右子结点标号为 \(2 * rt\) 和 \(2 * rt + 1\) 。对于本题，若有 \(u\) 是 \(v\) 的父亲，那么理论上 \(u\) 在 \(v\) 所建好的线段树的基础上只会影响一条链的结点，为保证不影响在 \(v\) 结点建好的线段树，对于产生影响的结点我们新建一个结点，并设置左右子结点，对于其它的结点，我们都可以复用，即将左右子结点直接指向已经建好的线段树的结点即可。

code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

const int INF = 2e9 + 10;

int a[N], sz, rot[N * 50], dep[N];

struct node {

    int l, r, val;

    void init() { l = r = 0; val = INF; }

}nd[N * 50];

vector<int> G[N];

void update(int p, int val, int l, int r, int &rt) {

    nd[rt = ++sz].init();

    nd[rt].val = min(nd[rt].val, val);

    if(l != r) {

        int m = l + r >> 1;

        if(p <= m) update(p, val, l, m, nd[rt].l);

        else update(p, val, m + 1, r, nd[rt].r);

        nd[rt].val = min(nd[nd[rt].l].val, nd[nd[rt].r].val);

    }

}

int query(int L, int R, int l, int r, int rt) {

    if(L <= l && R >= r) return nd[rt].val;

    int m = l + r >> 1;

    int res = INF;

    if(L <= m) res = query(L, R, l, m, nd[rt].l);

    if(R > m) res = min(res, query(L, R, m + 1, r, nd[rt].r));

    return res;

}

int mergeUp(int u, int v) {

    if(!u) return v;

    if(!v) return u;

    int t = ++sz;

    nd[t].init();

    nd[t].l = mergeUp(nd[u].l, nd[v].l);

    nd[t].r = mergeUp(nd[u].r, nd[v].r);

    nd[t].val = min(nd[u].val, nd[v].val);

    return t;

}

void dfs(int fa, int u) {

    dep[u] = dep[fa] + 1;

    update(dep[u], a[u], 1, N, rot[u]);

    for(int v : G[u]) {

        if(v != fa) {

            dfs(u, v);

            rot[u] = mergeUp(rot[u], rot[v]);

        }

    }

}

int main() {

    nd[0].init();

    int n, r;

    scanf("%d%d", &n, &r);

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

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

    }

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

        int u, v;

        scanf("%d%d", &u, &v);

        G[u].push_back(v);

        G[v].push_back(u);

    }

    dfs(0, r);

    int q, lst = 0;

    scanf("%d", &q);

    while(q--) {

        int x, k, b, c;

        scanf("%d%d", &b, &c);

        x = ((b + lst) % n) + 1;

        k = (c + lst) % n;

        lst = query(dep[x], min(dep[x] + k, N), 1, N, rot[x]);

        printf("%d\n", lst);

    }

    return 0;

}