AcWing 241. 楼兰图腾
原题链接
简单
作者:
呵呵_5
,
2021-05-06 21:21:10
,
所有人可见
,
阅读 288
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int N =2E5+10;
int n;
int a[N],tr[N];//tr代表的是1到n出现的次数.
int great[N],lower[N];//代表大于i的数出现的次数.代表小于i的数出现的次数.
int lowbit(int x)//提取x的最后一位1.所对应的2的次幂.
{
return x&-x;
}
void add(int x,int k)//给序列中第x个数加上k
{
for(int i=x;i<=n;i+=lowbit(i))tr[i]+=k;
}
int sum(int x)//查询前x个数的和
{
int 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++)scanf("%d",&a[i]);
LL res1=0,res2=0;
for(int i=1;i<=n;i++)
{
int y=a[i];
add(y,1);
//在该i左边比y小or大的数出现的次数.
lower[i]=sum(y-1);
great[i]=sum(n)-sum(y);
}
LL t1=0,t2=0;
for(int i=n;i;i--)
{
int y=a[i];
t1+=great[i]*(LL)(sum(n)-sum(y)-great[i]);//比y大总数-左边比y大的=右边比y大的.
t2+=lower[i]*(LL)(sum(y-1)-lower[i]);//同理
}
printf("%lld %lld\n", t1, t2);
return 0;
}