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&#44;0&#44;sizeof(c));
for(int i=1;i&lt;=n;i++)add(a[i]&#44;1)&#44;L[i]=getsum(a[i]-1);

//让后面的数先出现，每次统计已经出现的有多少个比自己小的数的个数，等价于求R[i]
memset(c&#44;0&#44;sizeof(c));
for(int i=n;i&gt;=1;i--)add(a[i]&#44;1)&#44;R[i]=getsum(a[i]-1);

long long ans=0;for(int i=1;i&lt;=n;i++)ans+=L[i]*R[i];
printf("%lld\n"&#44;ans);
return 0;

}

</p>