AcWing 1215. 小朋友排队
原题链接
中等
作者:
戒骄戒躁@
,
2022-12-08 23:40:52
,
所有人可见
,
阅读 109
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10,M=1e5+1;
int tr[N];
int a[M];
int n;
int sum[M];
int lowbit(int x)
{
return x&-x;
}
void add(int x,int c)
{
for(int i=x;i<N;i+=lowbit(i))
tr[i]+=c;
}
int ask(int x)
{
LL res=0;
for(int i=x;i;i-=lowbit(i))
res+=tr[i];
return res;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i]++;
}
for(int i=1;i<=n;i++)
{
sum[i]+=ask(N-1)-ask(a[i]);
add(a[i],1);
}
memset(tr,0,sizeof tr);
for(int i=n;i>0;i--)
{
sum[i]+=ask(a[i]-1);
add(a[i],1);
}
LL re=0;
for(int i=1;i<=n;i++)
re+=(LL)(sum[i]+1)*sum[i]/2;
cout<<re<<endl;
return 0;
}