uva 1428 - Ping pong

树状数组初级用法：

//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #define INF 0x3fffffff #define inf -0x3f3f3f3f #define N 50010 #define M 100010 #define LL long long #define mod 95041567 using namespace std; int n, MAX; int arr[N], d[M], p[N], q[N]; int lowbit(int x){ return x & (- x); } int sum(int x){ int s = 0; while(x > 0){ s += d[x]; x -= lowbit(x); } return s; } void add(int x){ while(x <= MAX){ ++ d[x]; x += lowbit(x); } } int main() { //freopen("in.txt", "r", stdin); int n, t; scanf("%d", &t); while(t --){ scanf("%d", &n); MAX = 0; for(int i = 0; i < n; ++ i){ scanf("%d", &arr[i]); MAX = max(MAX, arr[i]); p[i] = q[i] = 0; } memset(d, 0, sizeof(d)); for(int i = 0; i < n; ++ i){ add(arr[i]); p[i] = sum(arr[i] - 1); } memset(d, 0, sizeof(d)); for(int i = n - 1; i >





= 0; -- i){ add(arr[i]); q[i] = sum(arr[i] - 1); } LL cnt = 0; for(int i = 0; i < n; ++ i){ cnt += (LL)p[i] * (n - i - 1 - q[i]) + (LL)(i - p[i]) * q[i]; } //cout<< cnt <