图片加载可能有点慢，请跳过题面先看题解，谢谢
考虑以 \(i\) 为裁判，假设在 \([1,i-1]\) 中，有 \(l[i]\) 个人的技能值比 \(i\) 低；在 \([i+1,n]\) 中，有 \(r[i]\) 个人技能值比 \(i\) 低
那么 \(i\) 能贡献的答案数为 \(ans[i]=l[i]*(n-i-r[i])+r[i]*(i-1-l[i])\) 所以答案为 \(\sum_{i=1}^{n}ans[i]\) 至于 \(l[i]\) 和 \(r[i]\)，用树状数组维护一下就好了//made by Hero_of_Someone#include#include #include #include #define ll long long#define il inline#define RG registerusing namespace std;il int gi(){ RG int x=0,q=1; RG char ch=getchar(); while( ( ch<'0' || ch>'9' ) && ch!='-' ) ch=getchar(); if( ch=='-' ) q=-1,ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x; }int T,n,a[20010],c[100010];int l[20010],r[20010],Max;il int lowbit(int x){return x&-x;}il void init(){ n=gi(),Max=0; memset(c,0,sizeof(c)); for(int i=1;i<=n;i++) a[i]=gi(),Max=max(Max,a[i]);}il int sum(int x){ RG int ret=0; while(x>0){ ret+=c[x]; x-=lowbit(x); } return ret;}il void add(int x){ while(x<=Max){ c[x]++; x+=lowbit(x); } }il void work(){ RG ll ans=0; for(int i=1;i<=n;i++) l[i]=sum(a[i]),add(a[i]); memset(c,0,sizeof(c)); for(int i=n;i;i--){ r[i]=sum(a[i]),add(a[i]); ans+=l[i]*(n-i-r[i])+r[i]*(i-1-l[i]); } printf("%lld\n",ans);}int main(){ T=gi(); while(T--){ init(); work(); } return 0; }