题解：P11885 [RMI 2024] 跑酷 / Jump Civilization

· · 题解

考虑对区间的包含关系建树。在这棵树上，从 i 走到 v_i 相当于走到当前节点子树内 dfn 的最大值 +1 的位置，从 i 走到 i+1 相当于走到当前节点的第一个儿子。

现在我们可以刻画从 i 到 j 的距离了，它是这样一个东西：从 lca 到 i 的路径上所有点的右兄弟数量之和，加上从 lca 到 j 的路径上所有点的左兄弟数量之和。

记 a_i 表示从 i 到根的路径上所有点的右兄弟数量之和，b_i 表示左兄弟数量之和，c_i 表示兄弟数量之和，那么从 i 到 j 的距离就是 a_i+b_j-c_{lca(i,j)}。然后就可以直接上 dsu 了。

时间复杂度 O(n\log^2n)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 300005;
int n, m;
int v[maxn];
int a[maxn], b[maxn], c[maxn];
int sz[maxn], son[maxn];
vector<int> s[maxn];
vector<int> d[maxn];
vector<int> tmp;
stack<int> st;
int ans[maxn];
struct BIT {
    int sum[maxn];
    int lowbit(int x) {return x & -x;}
    void update(int x, int val) {for (; x <= n + 1; x += lowbit(x)) sum[x] += val;}
    int query(int x) {int res = 0; for (; x > 0; x -= lowbit(x)) res += sum[x]; return res;}
} t1, t2;
void build() {
    st.push(0);
    for (int i = 1; i <= n; i++) {
        while (v[st.top()] < v[i]) st.pop();
        d[st.top()].push_back(i);
        st.push(i);
    }
}
void dfs1(int x) {
    sz[x] = 1;
    for (int i = 0; i < d[x].size(); i++) {
        int y = d[x][i];
        a[y] = a[x] + d[x].size() - i - 1, b[y] = b[x] + i + 1;
        c[y] = c[x] + d[y].size();
        dfs1(y); sz[x] += sz[y];
        if (son[x] == 0 || sz[y] > sz[son[x]]) son[x] = y;
    }
}
void clear(int x) {
    if (x) t1.update(b[x], -1);
    for (auto y : d[x]) clear(y);
}
void heige(int x) {
    tmp.push_back(x);
    for (auto y : d[x]) heige(y);
}
void dfs2(int x) {
    if (son[x] == 0) {t1.update(b[x], 1); return;}
    for (auto y : d[x])
        if (y != son[x]) {dfs2(y); clear(y);}
    dfs2(son[x]);
    vector<int> f;
    int p = 0;
    for (int i = d[x].size() - 1; i >= 0; i--) {
        int y = d[x][i];
        if (y == son[x]) {p = i; break;}
        tmp.clear(); heige(y);
        for (auto j : tmp) ans[j] += t2.query(min(m - a[j] + c[x], n + 1));
        for (auto j : tmp) t2.update(b[j], 1), s[son[x]].push_back(m - b[j] + c[x]), f.push_back(j);
    }
    for (auto y : f) t2.update(b[y], -1), t1.update(b[y], 1);
    for (int i = p - 1; i >= 0; i--) {
        int y = d[x][i];
        tmp.clear(); heige(y);
        for (auto j : tmp) ans[j] += t1.query(min(m - a[j] + c[x], n + 1));
        for (auto j : tmp) t1.update(b[j], 1);
    }
    ans[x] += t1.query(min(m + b[x], n + 1));
    if (x) t1.update(b[x], 1);
}
void dfs3(int x) {
    for (auto i : s[x])
        if (i >= 0) t2.update(min(i + 1, n + 1), 1);
    ans[x] += t2.query(n + 1) - t2.query(a[x]);
    for (auto y : d[x]) dfs3(y);
    for (auto i : s[x])
        if (i >= 0) t2.update(min(i + 1, n - 1), -1);
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i < n; i++) cin >> v[i];
    v[n] = n + 1, v[0] = n + 2;
    build();
    c[0] = d[0].size();
    dfs1(0); dfs2(0); dfs3(0);
    for (int i = 1; i <= n; i++) cout << ans[i] + 1 << ' ';
    cout << '\n';
    return 0;
}