P1637 三元上升子序列

链接：Miku

----------------------

对于这个题，我们对于每一个数i，分别求出所有比它小的，在它前面的和

比它大的，在它后面的，然后把这两个乘起来，然后再把这些积加起来就可以了

-----------------------

然而这样直接做复杂度太高了，我们要优化，仿照树状数组求逆序对的方法，我们就可以在可以接受的时间内求出并且解决问题了

------------------------

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
int a[30005];
int tree[30005];
int b[30005];
long long minn[30005];
long long ans;
bool cmp(const int &x,const int &y){//要考虑数字相同的情况 
    if(a[x]!=a[y])
    return a[x]<a[y];
    else
    return x>y;
}
int lowbit(int x){
    return x&-x;
}
void add(int x,int k){
    while(x<=n){
        tree[x]+=k;
        x+=lowbit(x);
    }
    return ;
}
int sum(int x){
    int ans=0;
    while(x){
        ans+=tree[x];
        x-=lowbit(x);
    }
    return ans;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        b[i]=i;
    }
    sort(b+1,b+1+n,cmp);
    for(int i=1;i<=n;++i){//求比它小的 
        add(b[i],1);
        minn[b[i]]=sum(b[i]-1);
    }
    memset(tree,0,sizeof(tree));
    for(int i=n;i>=1;--i){//倒着求，就是大的 
        add(b[i],1);
        minn[b[i]]*=sum(n)-sum(b[i]);//直接乘骑来 
    }
    for(int i=1;i<=n;++i){
        ans+=minn[i];
    }
    printf("%lld",ans);
    return 0;
}