记录编号	582677	评测结果	AAAAAAAAAAAAA
题目名称	[USACO20 Open Gold]Haircut	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.164 s
提交时间	2023-09-21 21:30:27	内存使用	0.00 MiB

#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
const int N = 1e5+10;
ll n,a[N];
ll c[N],s[N];
void add(int x,ll z){
    for(;x <= n;x += x&-x)c[x] += z;
    return;
}
ll ask(int x){
    ll ans = 0;
    for(;x > 0;x -= x&-x)ans += c[x];
    return ans;
}
int main(){
    freopen("usaco_20Open_haircut.in","r",stdin);
    freopen("usaco_20Open_haircut.out","w",stdout);
    scanf("%lld",&n);
    for(int i = 1;i <= n;i++){
        scanf("%lld",&a[i]);
        add(n-a[i]+1,1);
        s[a[i]+1] += ask(n-a[i]);
    }//a[i]对在它之前比它大的值起作用，树状数组求前大致 
    int ans = 0;
    printf("0\n");
    for(int i = 1;i < n;i++){
        ans += s[i];
        printf("%lld\n",ans);
    }
    
    return 0;
    
}