1、找a[i]<a[j]<a[k]且i<j<k，不妨先找a[i]<a[j]。

可以将a数组倒过来看，树状数组维护它的每一个元素的逆序对个数，即在每一个数之前有多少个数比它小。

对每一个k(1<=k<=n)，暴力j（1<=j<=k）找到a[j]<a[k]，ans不断加上ask(j-1)。

附上90分代码：

#include<bits/stdc++.h>
using namespace std;
#define RI register int
#define LL long long
const int N=3e4+5;
int m,sum,c[N],k,cc[N];
LL n,a[N],b[N],d[N],ans;
LL read(){
    LL ss=0;char cc=getchar();
    for(cc;!isdigit(cc);cc=getchar());
    for(cc;isdigit(cc);cc=getchar()) ss=ss*10+cc-'0';
    return ss;
}
void dis(){
    sort(b+1,b+n+1);
    for(RI i=1;i<=n;++i) if(i==1||b[i]!=b[i-1]) d[++m]=b[i];
}
int lowbit(int x){
    return x&-x;
}
int ask(int x){
    sum=0;
    for(x;x;x-=lowbit(x)) sum+=c[x];
    return sum;
}
void add(int x){
    for(x;x<=m;x+=lowbit(x)) c[x]+=1;
}
int main(){
    n=read();
    for(RI i=1;i<=n;++i) b[i]=a[i]=read();
    dis();
    for(RI i=1;i<=n;++i){
        k=lower_bound(d+1,d+m+1,a[i])-d;
        cc[i]=ask(k-1);
        add(k);
        for(RI j=1;j<i;++j) if(a[j]<a[i]) ans+=cc[j];
    }
    printf("%lld\n",ans);
    return 0;
}

最后一个点TLE，开了O2还是TLE

2、优化暴力寻找j的过程

直接上代码：

#include<bits/stdc++.h>
using namespace std;
#define RI register int
#define LL long long
const int N=3e4+5;
int m,sum,c[N],k,cc[N];
LL n,a[N],b[N],d[N],ans,e[N];
LL read(){
    LL ss=0;char cc=getchar();
    for(cc;!isdigit(cc);cc=getchar());
    for(cc;isdigit(cc);cc=getchar()) ss=ss*10+cc-'0';
    return ss;
}
void dis(){
    sort(b+1,b+n+1);
    for(RI i=1;i<=n;++i) if(i==1||b[i]!=b[i-1]) d[++m]=b[i];
}
int lowbit(int x){
    return x&-x;
}
int ask(int x){
    sum=0;
    for(x;x;x-=lowbit(x)) sum+=c[x];
    return sum;
}
void add(int x){
    for(x;x<=m;x+=lowbit(x)) c[x]+=1;
}
void wk(int x,int lim,int st){//递归
    int kk=upper_bound(e+st,e+lim,x)-e;//e数组是a数组乘上-1的结果，则找a[j]<a[k]实际上就是找e[j]>e[k]，这里使用upper_bound函数
    if(kk!=lim){
            e[kk]=x;//将e[kk]减小为x，保证下一次不会再找到它
        ans+=cc[kk];
        if(kk+1<lim) wk(x,lim,kk+1);
        e[kk]=-a[kk];//还原e[kk]
    }
}
int main(){
    n=read();
    for(RI i=1;i<=n;++i){
        b[i]=a[i]=read();e[i]=-a[i];//这里首先将a数组乘上-1
    }
    dis();
    for(RI i=1;i<=n;++i){
        k=lower_bound(d+1,d+m+1,a[i])-d;
        cc[i]=ask(k-1);
        add(k);
        if(i>=3) wk(e[i],i,1);
    }
    printf("%lld\n",ans);
    return 0;
}

找了好久找不到错误问题所在，WA了8个点

求大佬帮忙指出问题所在