P11364 题解

· · 题解

这是一篇两只 \log 但是常数巨大的题解。

发现区间更大一定不优，所以本质上是在求 [l,r] 内所有长度为 k 的子区间的 \text{LCA*} 的最大值。

首先考虑 A 性质，此时区间 LCA 等于区间深度最小值。注意到这是经典的最小值最大问题，考虑二分答案 x。如果将 \text{dep}_i \ge x 的 i 全部赋为 1，其余的赋为 0，那么合法相当于有一个长度至少为 k 的全 1 区间。这个的判定可以用主席树做，注意要从后往前更新。

考场上的我止步于此。

这时需要注意到一个结论：

令 a_i=\text{dep}_{\text{LCA}(i, i+1)}，那么对于 l<r 有 \text{dep}_{\text{LCA*}(l, r)}=\min\limits_{i=l}^{r-1}a_i。

简短的证明：

这个时候只需要把之前维护的 \text{dep} 改成 a 就行了，需要注意特判 k=1 的情况。

时间复杂度 O(n \log^2 n)，空间复杂度 O(n \log n)，但是因为常数太大，无法通过。

代码：

#include <bits/stdc++.h>
using namespace std;
#define MAXN 500005
#define MAXK 19

int n, q;
int fa[MAXN], siz[MAXN], son[MAXN], top[MAXN], dep[MAXN], rt[MAXN], a[MAXN], id[MAXN]; int f[MAXN][MAXK];
vector<int> e[MAXN], vec[MAXN];

void dfs1(int x, int f){
    dep[x] = dep[fa[x]=f]+(siz[x]=1);
    for (auto i: e[x]) if (i ^ f){
        dfs1(i, x); siz[x] += siz[i]; if (siz[i] > siz[son[x]]) son[x] = i;
    }
}
void dfs2(int x, int tp){
    top[x] = tp; if (son[x]) dfs2(son[x], tp); for (auto i: e[x]) if (i != son[x] && i != fa[x]) dfs2(i, i);
}
int LCA(int x, int y){
    for (; top[x]^top[y]; x=fa[top[x]]) if (dep[top[x]] < dep[top[y]]) swap(x, y); return dep[x] < dep[y] ? x : y;
}
int qry(int l, int r){int k(__lg(r-l+1)); return max(f[l][k], f[r-(1<<k)+1][k]);}

namespace Seg{
    int ct; struct Node{int lmx, rmx, ans, s;}; struct T{Node p; int ls, rs;}tr[MAXN<<5];
    Node merge(Node a, Node b){
        return {a.lmx == a.s ? a.s+b.lmx : a.lmx, b.rmx == b.s ? b.s+a.rmx : b.rmx,
                max({a.ans, b.ans, a.rmx+b.lmx}), a.s+b.s};
    }
    void push_up(int p){tr[p].p = merge(tr[tr[p].ls].p, tr[tr[p].rs].p);}
    void build(int &p, int l, int r){
        p = ++ct; if (l == r){tr[p].p = {0, 0, 0, 1}; return;} int mid((l+r)>>1);
        build(tr[p].ls, l, mid); build(tr[p].rs, mid+1, r); push_up(p);
    }
    void modify(int &p, int l, int r, int x){
        tr[++ct] = tr[p]; p = ct; if (l == r){tr[p] = {1, 1, 1, 1}; return;} int mid((l+r)>>1);
        if (x <= mid) modify(tr[p].ls, l, mid, x); else modify(tr[p].rs, mid+1, r, x); push_up(p);
    }
    Node qry(int p, int l, int r, int L, int R){
        if (L <= l && r <= R) return tr[p].p; int mid((l+r)>>1); Node res = {0, 0, 0, 0};
        if (L <= mid) res = merge(res, qry(tr[p].ls, l, mid, L, R));
        if (R > mid) res = merge(res, qry(tr[p].rs, mid+1, r, L, R)); return res;
    }
}

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

    cin >> n; for (int i(1), u, v; i<n; ++i) cin >> u >> v, e[u].push_back(v), e[v].push_back(u); dfs1(1, 0); dfs2(1, 1);
    for (int i(1); i<=n; ++i) f[i][0] = dep[i]; for (int i(1); i<n; ++i) a[i] = dep[LCA(i, i+1)];
    for (int j(1); j<MAXK; ++j) for (int i(1); i+(1<<j)-1<=n; ++i) f[i][j] = max(f[i][j-1], f[i+(1<<(j-1))][j-1]);
    iota(id+1, id+n, 1); sort(id+1, id+n, [](int x, int y){return a[x] < a[y];});
    Seg::build(rt[n], 1, n); for (int i(n-1); i; --i) Seg::modify(rt[i]=rt[i+1], 1, n, id[i]);

    cin >> q;
    for (int x, y, k; q; --q){
        cin >> x >> y >> k; if (k == 1){cout << qry(x, y) << '\n'; continue;}
        int l(1), r(n-1), mid;
        while (l < r){
            mid = (l+r+1) >> 1; if (Seg::qry(rt[mid], 1, n, x, y-1).ans >= k-1) l = mid; else r = mid-1;
        }
        cout << a[id[l]] << '\n';
    }

    return 0;
}