树状数组
枚举裁判位置，设裁判为第i 个人，左边有l[i]个比他小的选手，右边有r[i]个比他小的选手；
令c[i]表示技能值为i 的人是否存在，计算l[i] 即c[1]~c[i-1]的和，计算l[i]后使c[a[i]]=1；同理求r[i]；
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 const int maxn = 100005; 7 8 int n; 9 int a[maxn]; 10 long long c[maxn]; 11 long long l[maxn],r[maxn]; 12 13 int lowbit (int x){ 14 return x&(-x); 15 } 16 17 void add (int x,long long d){ 18 while (x<=maxn-5){ //这里是我坑了很久的地方。。。这里的边界是技能值边界。。。 19 c[x]+=d; 20 x+=lowbit(x); 21 } 22 } 23 24 long long sum (int x){ 25 long long ans=0; 26 while (x>0){ 27 ans+=c[x]; 28 x-=lowbit(x); 29 } 30 return ans; 31 } 32 33 int main (){ 34 int t; //while (cin>>t) cout<<lowbit(t)<<endl; 35 cin>>t; 36 while (t--){ 37 cin>>n; 38 for (int i=1;i<=n;i++){ 39 cin>>a[i]; 40 } 41 memset (c,0,sizeof c); 42 for (int i=1;i<=n;i++){ 43 l[i]=sum(a[i]); 44 add (a[i],1); 45 } 46 memset (c,0,sizeof c); 47 for (int i=n;i>=1;i--){ 48 r[i]=sum(a[i]); 49 add (a[i],1); 50 } 51 long long ans=0; 52 for (int i=1;i<=n;i++) 53 ans+=l[i]*(n-i-r[i])+(i-l[i]-1)*r[i];//cout<<l[i]<<" "<<r[i]<<endl; 54 cout<<ans<<endl; 55 } 56 return 0; 57 }