#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std ;
const int N = ;
struct node{
int val,pos ;
}tmp[N];
int a[N] ;//离散化后的原始数组
int c[N] ;//树状数组
bool cmp(node st1,node st2){
return st1.val < st2.val ;
}
int lowbit(int x){//取得最右边的一个1
return x&(-x) ;
}
int getSum(int x){//区间1~x的和 log(N)
int sum = ;
for(int i=x;i>;i-=lowbit(i)){
sum += c[i] ;
}
return sum ;
}
void update(int x,int v){//单点更新 log(N)
for(int i=x;i<=N;i+=lowbit(i)){
c[i] += v ;
}
}
int main(){
int n, x ;
cin >> n ;
memset(c,,sizeof c) ;
for(int i=;i<n;i++){
cin >> tmp[i].val ;
tmp[i].pos = i ;
}
sort(tmp,tmp+n,cmp) ;
for(int i=;i<n;i++){
if(i== || tmp[i-].val != tmp[i].val)
a[tmp[i].pos] = i + ;//离散化
else{
a[tmp[i].pos] = a[tmp[i-].pos] ;
}
}
for(int i=;i<n;i++){
update(a[i],) ;
cout << getSum(a[i]-) << endl ;
}
return ;
}
算法笔记求序列A每个元素左边比它小的数的个数(树状数组和离散化)的相关教程结束。