Description

【题意】0x40数据结构进阶（0x42 树状数组）例题1：楼兰图腾
平面上有 $n(n≤2*10^5)$ 个点，每个点的横、纵坐标的范围都是 $1 \sim n$，任意两个点的横、纵坐标都不相同。
若三个点 $(x1,y1),(x2,y2),(x3,y3)$ 满足 $x1<x2<x3, y1>y2$ 并且 $y3 >y2$，则称这三个点构成“v”字图腾。
若三个点 $(x1,y1),(x2,y2),(x3,y3)$ 满足 $x1<x2<x3, y1<y2$ 并且 $y3 <y2$，则称这三个点构成“^”字图腾。
求平面上“v”和“^”字图腾的个数。
因此，你需要编写一个程序来求出V的个数和∧的个数。

【输入格式】
第一行一个数$n$。
第二行是$n$个数，分别代表y1，y2,…,yn（默认 x1 < x2 < x3 < …… < xn ）。

【输出格式】
两个数，中间用空格隔开，依次为V的个数和∧的个数。

【输入样例】
5
1 5 3 2 4

【输出样例】
3 4

Hint

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+10;
int n,a[N],c[N+1],L[N];
//L[i]表示对于a[i]左边有多少个比它小
int lowbit(int x){return x&(-x);}
void add(int x,int k){for(;x<=n;x+=lowbit(x))c[x]+=k;}
int getsum(int x){int res=0;for(;x>=1;x-=lowbit(x))res+=c[x];return res;}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    memset(c,0,sizeof(c));
    for(int i=1;i<=n;i++)add(a[i],1),L[i]=getsum(a[i]-1);
LL ans=0;
for(int i=2;i&lt;n;i++)
{
	ans+=LL(i-1-L[i])*(n-a[i]-(i-1-L[i]));
}
printf("%lld "&#44;ans);
ans=0;
for(int i=2;i&lt;n;i++)
{
	ans+=LL(L[i])*(a[i]-1-L[i]);
}
printf("%lld\n"&#44;ans);
return 0;

}

</p>