「NOIP2024」树上查询

    「NOIP2024」树上查询

    Luogu P11364

    给出一棵包含 nn 个节点的树,以 11 为根。

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

    有 QQ 次查询,每次查询给出三个整数 l,r,kl, r, k,你需要求出

    max⁡l≤l′≤r′≤r∧r′−l′+1≥kdepLCA∗(l′,r′)\max\limits_{l \leq l' \leq r' \leq r \land r' - l' + 1 \geq k} \mathrm{dep}_{\mathrm{LCA}^{*}(l', r')}

    数据范围:1≤n,Q≤5×1051 \leq n, Q \leq 5 \times 10^5,1≤l≤r≤n1 \leq l \leq r \leq n,1≤k≤r−l+11 \leq k \leq r - l + 1。

    时空限制:22s / 10241024MiB。

    Solution

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

    结论

    对于 l<rl < r 的区间 [l,r][l, r],有

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

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

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

    max⁡l≤l′≤r′≤r∧r′−l′+1≥k{min⁡l′≤i≤r′vi}\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\}

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

    (仔细思考可以发现,如果交集不包含 ii 也没有关系,由笛卡尔树结构此时肯定会找到 ≥vi\geq v_i 的答案)

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

    第一类:yi>ry_i > r

    此时有:

    yi>rxi≤r−k+1y_i > r \\ x_i \leq r - k + 1

    第二类:yi≤ry_i \leq r

    此时有:

    l+k−1≤yi≤ryi−xi+1≥kl + k - 1 \leq y_i \leq r \\ y_i - x_i + 1 \geq k

    两类情况均可扫描线。第一类情况,将 rr 从右扫到左;第二类情况,将 kk 从大扫到小。

    时间复杂度 O(nlog⁡n)\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;
    }
    
    /**
     *  心中无女人
     *  比赛自然神
     *  模板第一页
     *  忘掉心上人
    **/