Promotion Counting

因为子树在遍历数组上是连续的区间，所以问题就转化为在区间上求大于一个值的元素个数的问题。
怎么求的关键点，是用离线法（Milk Visits也用了这个方法），把元素从大到小往线段树中添加值为1的flags，然后就直接区间求和就行了。
元素值是唯一的，所以比较友好。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n;
pi p[100005];
vector<int> adj[100005];
int st[100005], en[100005];     // range of subtree in traversal array
int ans[100005];
int tree[200005];               // segment tree over traversal array for 
                                // flags of values less than current
 
void set(int k, int x) {
    k += n;
    tree[k] = x;
    for (k /= 2; k >= 1; k /= 2) {
        tree[k] = tree[2*k]+tree[2*k+1];
    }
}
 
int sum(int a, int b) {
    a += n; b += n;
    int s = 0;
    while (a <= b) {
        if (a%2 == 1) s += tree[a++];
        if (b%2 == 0) s += tree[b--];
        a /= 2; b /= 2;
    }
    return s;
}
 
int ti;
void dfs(int s) {
    st[s] = ti++;
    for (int u: adj[s])
        dfs(u);
    en[s] = ti-1;
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &p[i].first);
        p[i].second = i;
    }
    for (int i = 1; i < n; i++) {
        int fa;
        scanf("%d", &fa);
        adj[fa-1].push_back(i);        
    }
    dfs(0);     // find st and en for each subtree
    sort(p, p+n, greater<pi>());   // decreasing
    for (int i = 0; i < n; i++) {   // adding nodes by decreasing p values and count
        int id = p[i].second, pv = p[i].first;
        ans[id] = sum(st[id], en[id]);
        set(st[id], 1);
    }
    for (int i = 0; i < n; i++)
        printf("%d\n", ans[i]);
    return 0;
}
 
 
/*
Example:
 
      1 (80)
     / \
(84)2   3(68)
    |   |
(71)4   5(95)
 
*/