「NOIP2024」树上查询

发表于 2025-09-01 分类于 NOIP 本文字数： 1.5k 阅读时长 ≈ 6 分钟

Description

给出一棵包含 $n$ 个节点的树，以 $1$ 为根。

定义 $\mathrm{dep}_u$ 表示节点 $u$ 的深度，定义 $\mathrm{LCA}^{*}(l, r)$ 表示区间 $[l, r]$ 中所有节点的最近公共祖先。

有 $Q$ 次查询，每次查询给出三个整数 $l, r, k$ ，你需要求出

\max\limits_{l \leq l' \leq r' \leq r \land r' - l' + 1 \geq k} \mathrm{dep}_{\mathrm{LCA}^{*}(l', r')}

数据范围： $1 \leq n, Q \leq 5 \times 10^5$ ， $1 \leq l \leq r \leq n$ ， $1 \leq k \leq r - l + 1$ 。

时空限制： $2$ s / $1024$ MiB。

膜拜 CLYZ 大神学弟 hhz，爆切此题。

Solution

结论：对于 $l < r$ 的区间 $[l, r]$ ，有

\mathrm{dep}_{\mathrm{LCA}^{*}(l, r)} = \min\limits_{l \leq i < r} \mathrm{dep}_{\mathrm{LCA}(i, i + 1)}

证明：我们考虑证明至少有一个 $l \leq i < r$ 对应的 $\mathrm{LCA}(i, i + 1)$ 可以取到 $\mathrm{LCA}^{*}(l, r)$ 。将区间 $[l, r]$ 中的所有点，按照 $\mathrm{LCA}^{*}(l, r)$ 的子树划分进行染色，不难发现区间 $[l, r]$ 中必定有相邻异色的点对 $i, i + 1$ （否则整个区间只有一种颜色），此时 $i, i + 1$ 来自 $\mathrm{LCA}^{*}(l, r)$ 的不同子树，故有 $\mathrm{LCA}(i, i + 1) = \mathrm{LCA}^{*}(l, r)$ 。

首先特判掉 $k = 1$ 的情况。对于 $k > 1$ 的情况，我们先令 $r, k$ 都减去 $1$ ，记 $v_i = \mathrm{dep}_{\mathrm{LCA}(i, i + 1)}$ ，我们要求的即为

\max\limits_{l \leq l' \leq r' \leq r \land r' - l' + 1 \geq k} \left\{ \min\limits_{l' \leq i \leq r'} v_i \right\}

考虑对 $v_i$ 建出笛卡尔树（小根堆），找出以 $v_i$ 为最小值的极长区间 $[x_i, y_i]$ 。对于一个询问 $l, r, k$ ，只需要区间 $[l, r]$ 与 $[x_i, y_i]$ 的交集大小 $\geq k$ ，则对答案就有 $v_i$ 的贡献。

（仔细思考可以发现，如果交集不包含 $i$ 也没有关系，由笛卡尔树结构此时肯定会找到 $\geq v_i$ 的答案）

现在就是要考虑如何处理交集关系？可以按照右端点的位置关系分类。

第一类： $y_i > r$

此时有：

y_i > r \\ x_i \leq r - k + 1

第二类： $y_i \leq r$

此时有：

l + k - 1 \leq y_i \leq r \\ y_i - x_i + 1 \geq k

两类情况均可扫描线。第一类情况，将 $r$ 从右扫到左；第二类情况，将 $k$ 从大扫到小。

时间复杂度 $\mathcal{O}(n \log n)$ 。

#include <bits/stdc++.h>

#define debug(a) std::cout << #a << "=" << (a) << ' '

using s64 = long long;
using u64 = unsigned long long;

/* 取 min */
template <class T>
inline void chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
    }
}
/* 取 max */
template <class T>
inline void chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
    }
}

/* ----- ----- ----- 正文 ----- ----- ----- */

const int N = 500100;

int n, Q;

struct Graph {
    std::vector< std::vector<int> > table;

    void init(int _n) {
        table.assign(_n + 1, {});
    }

    void add_edge(int u, int v) {
        table[u].push_back(v);
    }
} G;

int dep[N];
int anc[20][N];

void dfs_init(int u, int fu) {
    dep[u] = dep[fu] + 1;
    anc[0][u] = fu;
    for (int i = 1; i <= 19; i ++) anc[i][u] = anc[i - 1][anc[i - 1][u]];

    for (int v : G.table[u]) {
        if (v == fu) continue;
        dfs_init(v, u);
    }
}

int lca(int x, int y) {
    if (dep[x] > dep[y]) std::swap(x, y);
    for (int i = 19; i >= 0; i --)
        if (dep[x] <= dep[anc[i][y]]) y = anc[i][y];
    if (x == y) return x;
    for (int i = 19; i >= 0; i --)
        if (anc[i][x] ^ anc[i][y]) x = anc[i][x], y = anc[i][y];
    return anc[0][x];
}

int value[N];

namespace dkr {
    int rt;
    struct node {
        int lc, rc;
        int le, rg;
    } t[N];

    int top, stk[N];
    void build() {
        for (int i = 1; i < n; i ++) {
            int k = top;
            while (k && value[stk[k]] > value[i]) k --;

            if (k) t[stk[k]].rc = i;
            if (k < top) t[i].lc = stk[k + 1];

            stk[top = k + 1] = i;
        }
        rt = stk[1];
    }

    void dfs_init(int u) {
        t[u].le = t[u].rg = u;
        if (t[u].lc) {
            dfs_init(t[u].lc);
            t[u].le = t[t[u].lc].le;
        }
        if (t[u].rc) {
            dfs_init(t[u].rc);
            t[u].rg = t[t[u].rc].rg;
        }
    }
}

namespace SGT {
    struct node {
        int max;
    } t[N * 4];

    void build(int p, int l, int r) {
        if (l == r) {
            t[p].max = dep[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(p * 2, l, mid), build(p * 2 + 1, mid + 1, r);
        t[p].max = std::max(t[p * 2].max, t[p * 2 + 1].max);
    }

    void init(int p, int l, int r) {
        t[p].max = 0;
        if (l == r) return;
        int mid = (l + r) >> 1;
        init(p * 2, l, mid), init(p * 2 + 1, mid + 1, r);
    }
    
    void change(int p, int l, int r, int x, int y) {
        chmax(t[p].max, y);
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (x <= mid) {
            change(p * 2, l, mid, x, y);
        } else {
            change(p * 2 + 1, mid + 1, r, x, y);
        }
    }

    int ask(int p, int l, int r, int s, int e) {
        if (s <= l && r <= e) {
            return t[p].max;
        }
        int mid = (l + r) >> 1;
        if (s <= mid && mid < e) {
            return std::max(ask(p * 2, l, mid, s, e), ask(p * 2 + 1, mid + 1, r, s, e));
        }
        if (s <= mid) {
            return ask(p * 2, l, mid, s, e);
        } else {
            return ask(p * 2 + 1, mid + 1, r, s, e);
        }
    }
}

std::vector< std::tuple<int, int, int, int> > seq;
int ans[N];

void scan1() {
    std::vector< std::vector< std::tuple<int, int> > > qry(n + 1);
    std::vector< std::vector< std::tuple<int, int> > > scan(n + 1);
    
    for (auto [l, r, k, id] : seq) {
        qry[r].push_back({r - k + 1, id});
    }

    for (int i = 1; i < n; i ++) {
        int x = dkr::t[i].le, y = dkr::t[i].rg, v = value[i];
        scan[y].push_back({x, v});
    }

    SGT::init(1, 1, n);
    for (int i = n; i >= 1; i --) {
        if (i < n) {
            for (auto [x, v] : scan[i + 1]) {
                SGT::change(1, 1, n, x, v);
            }
        }
        for (auto [l, id] : qry[i]) {
            chmax(ans[id], SGT::ask(1, 1, n, 1, l));
        }
    }
}

void scan2() {
    std::vector< std::vector< std::tuple<int, int, int> > > qry(n + 1);
    std::vector< std::vector< std::tuple<int, int> > > scan(n + 1);

    for (auto [l, r, k, id] : seq) {
        qry[k].push_back({l + k - 1, r, id});
    }

    for (int i = 1; i < n; i ++) {
        int x = dkr::t[i].le, y = dkr::t[i].rg, v = value[i];
        scan[y - x + 1].push_back({y, v});
    }

    SGT::init(1, 1, n);
    for (int i = n; i >= 1; i --) {
        for (auto [y, v] : scan[i]) {
            SGT::change(1, 1, n, y, v);
        }
        for (auto [l, r, id] : qry[i]) {
            chmax(ans[id], SGT::ask(1, 1, n, l, r));
        }
    }
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    std::cin >> n;

    G.init(n);
    for (int i = 1; i < n; i ++) {
        int x, y;
        std::cin >> x >> y;

        G.add_edge(x, y), G.add_edge(y, x);
    }

    /* 预处理 le[], rg[], value[] */

    dfs_init(1, 0);

    for (int i = 1; i < n; i ++) {
        value[i] = dep[lca(i, i + 1)];
    }

    dkr::build();
    dkr::dfs_init(dkr::rt);

    // for (int i = 1; i < n; i ++) {
    //     int x = dkr::t[i].le, y = dkr::t[i].rg, v = value[i];
    //     std::cout << ' ' << x << ' ' << y << ' ' << v << '\n';
    // }
    
    /* 统计答案 */

    SGT::build(1, 1, n);

    std::cin >> Q;

    for (int i = 1; i <= Q; i ++) {
        int l, r, k;
        std::cin >> l >> r >> k;

        if (k == 1) {
            ans[i] = SGT::ask(1, 1, n, l, r);
        } else {
            r --, k --;
            seq.push_back({l, r, k, i});
        }
    }

    scan1();
    scan2();

    for (int i = 1; i <= Q; i ++) {
        std::cout << ans[i] << '\n';
    }

    return 0;
}

/**
 *  心中无女人
 *  比赛自然神
 *  模板第一页
 *  忘掉心上人
**/

Description

Solution

第一类：yi>ry_i > ryi​>r

第二类：yi≤ry_i \leq ryi​≤r

第一类： $y_i > r$

第二类： $y_i \leq r$