AcWing 1215. 小朋友排队
原题链接
中等
作者:
鑫霜
,
2022-02-20 16:25:27
,
所有人可见
,
阅读 113
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e6+5;
#define ll long long
#define endl '\n'
int sum[N],tr[N],a[N];
int n;
int lowbit(int x){return x&-x;}
//因为 tr树状数组是以坐标x作为下标识 而不是 i作为下标, 所以tr里存的前缀和是数量
void add(int x,int v){
for(int i=x;i<N;i+= lowbit(i))tr[i]++;
}
int query(int x){
int res=0;
for(int i=x;i>0;i-= lowbit(i))res+=tr[i];
return res;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i],a[i]++;
/*
这里下面这两行可能会有疑惑,
比如add,sum 为什么要每一步求,在后面为什么要重新初始化
注意,我们sum数组里面,下标是i
而tr数组里,下标是x
要是不像这样算的话,i对应的x会很混乱,会污染tr数组之类的,反正会出问题
*/
sum[i]+= query(N-1)- query(a[i]);
add(a[i],1);
}
memset(tr,0,sizeof tr);
for(int i=n;i>=1;i--){
sum[i]+= query(a[i]-1);
add(a[i],1);
}
ll ans=0;
for(int i=1;i<=n;i++){
ans+=(ll)(sum[i]+1)*sum[i]/2;
}
cout<<ans<<endl;
return 0;
}