[USACO17JAN]Promotion Counting P 题解

题目描述

给你一棵树，每个点有一个点权 \(p_i\)，求 \(\forall i\)，\(i\) 的子树内点权比 \(i\) 的点权大的点的数量。

思路

看到子树我就忍不住了，不得不狠狠地吧树拍到 \(dfn\) 序上了，发现用 \(dfn\) 拍扁之后，变成了求区间小于 \(x\) 元素个数的统计问题，分块可做。

另一个更优秀的离线做法是：

用树状数组维护点对答案的贡献，初始时所有点的树状数组设为 \(0\)。

按点权从大到小的顺序选取所有点
统计这个点子树内的所有贡献和（子树和）
在树状数组中给这个点的贡献设为 \(1\)。

正确性证明：

题目中的约束有二。

合法的点应在 \(i\) 的子树内；

合法的点的点权应大于 \(i\)。

我们从大到小地选取点保证了第二个约束，也就是所有点权大于 \(i\) 的点所给的贡献都被考虑到了。

那么处理第一个约束只需要用树状数组维护 \(dfn\) 就可以了。

时间复杂度：\(O(n\log n)\)

// Problem: P3605 [USACO17JAN]Promotion Counting P
// URL: https://www.luogu.com.cn/problem/P3605
// Author: Moyou
// Copyright (c) 2023 Moyou All rights reserved.
// Date: 2023-04-23 22:49:40

#include <algorithm>
#include <iostream>
#include <vector>
#define speedup (ios::sync_with_stdio(0), cin.tie(0), cout.tie(0))
using namespace std;

const int N = 1e5 + 10;

struct node
{
    int id, w;
} a[N];

vector<int> g[N];

int dfn[N], idx, sz[N];

void dfs(int u)
{
    dfn[u] = ++ idx;
    sz[u] = 1;
    for(auto v : g[u])
        dfs(v), sz[u] += sz[v];
}

int n;

struct BIT
{
    int tr[N];
    inline int lowbit(int x) { return x & -x; }

    inline void update(int i, int c) // 位置x加c
    {
        for (; i <= n; i += lowbit(i))
            tr[i] += c;
    }

    inline int query(int i) // 返回前x个数的和
    {
        int res = 0;
        for (; i; i &= i - 1) // 等价于i -= lowbit(i)
            res += tr[i];
        return res;
    }
} bit;

int ans[N];

signed main()
{
    n = read();
    for(int i = 1; i <= n; i ++)    
        a[i].w = read(), a[i].id = i;
        
    for(int i = 2, a; i <= n ; i ++)
        a = read(), g[a].push_back(i);
        
    sort(a + 1, a + n + 1, [](node a, node b){return a.w > b.w; });
    
    dfs(1);
    
    for(int i = 1; i <= n; i ++)
    {
        int id = a[i].id;
        ans[id] = bit.query(dfn[id] + sz[id] - 1) - bit.query(dfn[id] - 1);
        bit.update(dfn[id], 1);
    }
    
    for(int i = 1; i <= n; i ++)
        write(ans[i]), putchar('\n');
        
    return 0;
}