acwing1215. 小朋友排队

题目

题解

• 要将某个数排好序，只需要交换比他大的数和比他小的数
• 每个数被交换了k次，那么不高兴度为k*k(+1)/2

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e6+10;
int n,h[N],tr[N],sum[N];

int lowbit(int x){
    return x&-x;
}
void add(int x,int v){
    for(int i=x;i<N;i+=lowbit(i))tr[i]+=v;
}
int query(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i))res+=tr[i];
    return res;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)scanf("%d",&h[i]),h[i]++;
    for(int i=0;i<n;i++){
        sum[i]=query(N-1)-query(h[i]);
        add(h[i],1);
    }
    memset(tr,0,sizeof tr);
    for(int i=n-1;i>=0;i--){
        sum[i]+=query(h[i]-1);
        add(h[i],1);
    }
    long long ans=0;
    for(int i=0;i<n;i++)ans+=(long long )sum[i]*(sum[i]+1)/2;
    cout<<ans<<endl;
    
    return 0;
}