树状数组

枚举裁判位置，设裁判为第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 
     
       2 #include 
      
        3 #include 
       
         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<
        
         <
         
          >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<
          
           <<" "<
           
            <