Luogu3605 [USACO17JAN]Promotion Counting晋升者计数

给一棵 \(n\) 个点的树，点 \(i\) 有一个权值 \(a_i\) 。对于每个 \(i\) ，求 \(\displaystyle\sum_{j\in subtree(i)}{[a_i<a_j]}\)

\(n\leq10^5,\ fa_i<i\)

树状数组

---

树上逆序对？一眼线段树合并、、、空间没毛病、、

回想求序列逆序对的过程，发现在树上做时只需减去树状数组中以往的贡献，于是便可以愉快地树状数组搞了

时间复杂度 \(O(n\log n)\) ，空间复杂度 \(O(n)\)

#include <bits/stdc++.h>

using namespace std;

#define nc getchar()

const int maxn = 1e5 + 10;

int n, a[maxn], dat[maxn], c[maxn], ans[maxn]; vector <int> e[maxn];

inline int read() {

  int x = 0; char c = nc;

  while (c < 48) c = nc;

  while (c > 47) x = x * 10 + c - 48, c = nc;

  return x;

}

void upd(int pos) {

  for (; pos <= n; pos += pos & -pos) {

    c[pos]++;

  }

}

int query(int pos) {

  int res = 0;

  for (; pos; pos &= pos - 1) {

    res += c[pos];

  }

  return res;

}

void dfs(int u) {

  int lst = query(n) - query(a[u]); upd(a[u]);

  for (int v : e[u]) dfs(v);

  ans[u] = query(n) - query(a[u]) - lst;

}

int main() {

  n = read();

  for (int i = 1; i <= n; i++) {

    dat[i] = a[i] = read();

  }

  for (int i = 2; i <= n; i++) {

    e[read()].push_back(i);

  }

  sort(dat + 1, dat + n + 1);

  for (int i = 1; i <= n; i++) {

    a[i] = lower_bound(dat + 1, dat + n + 1, a[i]) - dat;

  }

  dfs(1);

  for (int i = 1; i <= n; i++) {

    printf("%d\n", ans[i]);

  }

  return 0;

}