Cod sursă (job #816533)

#include "bits/stdc++.h"
#define int long long
const int mtestcase = 0;
#define debug(x) #x << " = " << x << '\n'
const int SIZE = 3e5;
int n, root, v[SIZE + 5], in[SIZE  + 5], out[SIZE + 5], euler[SIZE + 5];
int ans[SIZE + 5];
std :: vector < int > adj[SIZE + 5];
int timer = 0;
struct Fenwick{
  int n, v[SIZE + 5];
  void Init(int n){
    this -> n = n + 1;
    for(int i = 0; i <= SIZE; i++){
      v[i] = 0;
    }
  }
  void Update(int idx, int val){
    for(int i = idx; i <= n; i += (i & -i)){
      v[i] += val;
    }
  }
  int Query(int idx){
    int sum = 0;
    for(int i = idx; i > 0; i -= (i & -i)){
      sum += v[i];
    }
    return sum;
  }
};
struct Queryy{
  int val, left, right, idx;
};
struct Node{
  int val, pos;
};
bool Cmp_query(Queryy a, Queryy b){
  return a.val > b.val;
}
bool Cmp_node(Node a, Node b){
  return a.val > b.val;
}
Node node[SIZE + 5];
Queryy queries[SIZE + 5];
void Dfs(int node){
  timer++;
  in[node] = timer;
  euler[timer] = node;
  for(auto i : adj[node]){
    Dfs(i);
  }
  out[node] = timer;
}
Fenwick aib;
void ReadInit(){
  std :: cin >> n;
  aib.Init(n + 1);
  for(int i = 1; i <= n; i++){
    std :: cin >> v[i];
  }
  for(int i = 1; i <= n; i++){
    int x;
    std :: cin >> x;
    if(x == 0){
      root = i;
    }else{
      adj[x].push_back(i);
    }
  }
  Dfs(root);
  for(int i = 1; i <= n; i++){
    node[i - 1] = {v[euler[i]], i};
  }
  for(int i = 1; i <= n; i++){
    queries[i - 1] = {v[i], in[i] + 1, out[i], i};
  }
}
void Sorting(){
  //offline
  std :: sort(node, node + n, Cmp_node);
  std :: sort(queries, queries + n, Cmp_query);
}
void testcase(){
  int j = 0;
  for(int i = 0; i < n; i++){
    while(j < n and node[j].val > queries[i].val){
      aib.Update(node[j].pos, +1);
      j++;
    }
    ans[queries[i].idx] = aib.Query(queries[i].right) - aib.Query(queries[i].left - 1);
  }
  for(int i = 1; i <= n; i++){
    std :: cout << ans[i] << " ";
  }
}
signed main(){
  #ifdef LOCAL
    freopen("input.txt", "r", stdin);
  #endif
  freopen("complexat.in", "r", stdin);
  freopen("complexat.out", "w", stdout);
  std :: ios_base :: sync_with_stdio(false);
  std :: cin.tie(0);
  if(mtestcase){
    int t;
    std :: cin >> t;
    while(t -- ){
      testcase();
    }
  }else{
    ReadInit();
    Sorting();
    testcase();
  }
  return 0;
}