暑期cspj模拟赛13

T3

原题没有题解,只有我的ac代码 如果在计算一下长链,可以优化空间

#include <bits/stdc++.h>
using namespace std;
// 查阅地址
// http://oi-wiki.com/lang/pb-ds/tree/
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef __gnu_pbds::tree<long long, __gnu_pbds::null_type, less<long long>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> gtree;

long long n, m;
long long a[100010];
vector<int> adj[100010];

int ans[100005];

void dfs(int ro, int p, gtree& gt) {
    bool flag = true;
    gtree gt2;
    for (int i = 0; i < adj[ro].size(); i++) {
        if (adj[ro][i] == p) {
            continue;
        }
        if (flag) {
            dfs(adj[ro][i], ro, gt);
            flag = false;
        }
        else {
            dfs(adj[ro][i], ro, gt2);
            for (auto v: gt2) {
                gt.insert(v);
            }
            gt2.clear();
        }
    }

    // 这个是返回大于a[ro]的个数
    ans[ro] = gt.size() - gt.order_of_key(a[ro] * 1000000 + 500000);

    // 这是一个不可重复的树    通过此方法插入就不会有重复的  为什么是乘以1000000   因为个数只有10万个，乘以1000000可以保证不会重复
    gt.insert(a[ro] * 1000000 + ro);
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 2; i <= n; i++) {
        int p;
        cin >> p;
        adj[p].push_back(i);
    }
    gtree gt;
    dfs(1, 0, gt);


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

    return 0;
}