*【树状数组】^三元组
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Description
【题意】给定一个数列$n$个数。其中如有三个元素$a_i，a_j，a_k$，满足$a_i<a_j>a_k（i<j<k）$，称为一个^三元组。求数列中^三元组的个数。
【输入格式】
第一行是一个数$n（1 \le n \le 50000）$，接下来$n$个元素$ai（0 \le a_i \le 32767）$。
【输出格式】
一个数，^三元组的个数。
【输入样例】
5
1 2 3 4 1
【输出样例】
6
Hint
#include<bits/stdc++.h>
using namespace std;
const int N=35000;
int n,a[51000],c[N+1],L[51000],R[51000];
//L[i]表示对于a[i]左边有多少个比它小
//R[i]表示对于a[i]右边有多少个比它小
int lowbit(int x){return x&(-x);}
void add(int x,int k)
{
while(x<=N)c[x]+=k,x+=lowbit(x);
}
int getsum(int x)
{
int s=0;
while(x>0)s+=c[x],x-=lowbit(x);
return s;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i]++;
//让前面的数先出现，每次统计已经出现的有多少个比自己小的数的个数，等价于求L[i]
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++)add(a[i],1),L[i]=getsum(a[i]-1);
//让后面的数先出现，每次统计已经出现的有多少个比自己小的数的个数，等价于求R[i]
memset(c,0,sizeof(c));
for(int i=n;i>=1;i--)add(a[i],1),R[i]=getsum(a[i]-1);
long long ans=0;for(int i=1;i<=n;i++)ans+=L[i]*R[i];
printf("%lld\n",ans);
return 0;
}
</p>