Haircut (USACO Gold 2020 US Open)

题意形式化表达就是：就是对每一个 $y$ ，求 $x<y$ ， $A_x>A_y$ 的 $x$ 数量 $C_y$ ，然后答案就是 $\sum_{A[y]<j} C_y$ 。

为了求 $C_y$ ，我们发现有个重要条件 $A_i \leq N$ ，所以可以直接用线段数来统计目前见过的大于某个数的所有数的数量：就是对 $A_x$ 的每个值计数，然后对于每个 $y$ ，统计 $[A_y+1, N]$ 的计数总和（range sum）。

有了 $C_y$ 之后， $j$ 从小到大累加就可以了。

复杂度是 $\mathcal{O}(N \log N)$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
ll cnt[100005];         // cnt[j], A[y]==j的cnt之和
ll ps[100005];          // prefix sum of cnt[]
ll tree[200005];
 
void add(int i, ll x) {     // segment tree update
    i += n;
    tree[i] += x;
    for (i /= 2; i > 0; i /= 2) 
        tree[i] = tree[i*2] + tree[i*2+1];
}
 
ll sum(int a, int b) {      // segment range sum
    ll res = 0;
    a += n, b += n;
    for (; a <= b; a /= 2, b /= 2) {
        if (a%2) res += tree[a++];
        if (b%2 == 0) res += tree[b--];
    }
    return res;
}
 
int main() {
    scanf("%d", &n);
    n++;
    for (int i = 0; i < n-1; i++) {
        int a;
        scanf("%d", &a);
        add(a, 1);
        cnt[a] += sum(a+1, n);
    }
    printf("0\n");
    for (int i = 0; i < n-2; i++) {
        ps[i+1] = ps[i] + cnt[i];
        printf("%lld\n", ps[i+1]);
    }
    return 0;
}