题意：给一组序列，从中找出一个四元组，使四个元素下标两两不同，且a<ｂ，ｃ＜ｄ有X_a < X_b , X_c > X_d。问一共有多少组满足要求的四元组。

思路：使用树状数组保存左边小于，左边大于，右边小于，右边大于当前位的数的个数。保存逆序对，顺序对组数。在逆序对X顺序对的结果中存在b,c为同一数，a,d为同一数，a,c为同一数，d,b为同一数的情况，将这些情况数量减去得到答案。

 

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 using namespace std;  6 const int N = 50005;  7 typedef long long LL;  8   9 int tmp[N] , arr[N]; 10 int n,cnt; //cnt为离散后不同数的个数 11 int ls[N],rs[N],rb[N],lb[N]; // ls：左边小于当前位的数的个数 ， rs：右边小于当前位的数的个数，lb：左边大于当前位的数的个数，rb：右边大于当前位的数的个数 12 int tls[N],trs[N],trb[N],tlb[N]; // 树状数组 13 LL ans,suml,sumb; //答案，逆序对个数，顺序对个数 14  15  16 void init() 17 { 18     memset(tls,0,sizeof (tls)); 19     memset(trs,0,sizeof (trs)); 20     memset(tlb,0,sizeof (tlb)); 21     memset(trb,0,sizeof (trb)); 22     ans = suml = sumb = 0; 23 } 24  25 LL getl(int p,int *tr) 26 { 27     LL res = 0; 28     while (p > 0) 29     { 30         res += (LL)tr[p]; 31         p -= (p&-p); 32     } 33     return res; 34 } 35  36 LL getr(int p,int *tr) 37 { 38     LL res = 0; 39     while (p <= cnt) 40     { 41         res += (LL)tr[p]; 42         p += (p&-p); 43     } 44     return res; 45 } 46  47 void upl(int p,int *tr) 48 { 49     while (p<=cnt) 50     { 51         tr[p] += 1; 52         p += (p&-p); 53     } 54 } 55  56 void upr(int p,int *tr) 57 { 58     while (p > 0) 59     { 60         tr[p] += 1; 61         p -= (p&-p); 62     } 63 } 64  65  66 int main() 67 { 68     while (scanf("%d",&n)==1) 69     { 70         init(); 71         for (int i=0;i
         
          =0;i--) 91         { 92             rb[i] = getr(arr[i]+1,trb); rs[i] = getl(arr[i]-1,trs); 93             upl(arr[i],trs); upr(arr[i],trb); 94         } 95          96         ans = suml * sumb; //逆序对数乘顺序对数，结果存在不合法的情况 97         for (int i=0;i