题目链接：https://vjudge.net/problem/UVALive-4329

题意：n个数，找出三个数ai,aj,ak，使得i<j<k且ai<aj<ak或者ai>aj>ak。问有多少种组合方法。

枚举aj，记cj为[1,j)内比aj小的数的个数，dj为(j,n]比aj小的个数。

那么j-1-cj为[1,j)比aj大的数的个数，n-j-dj为(j,n]比aj大的数的个数。

把答案就是∑dj*(j-1-cj)+(n-j-dj)*cj

用BIT在O(nlgn)就能分别获得c和d。

1 #include 
     
       2 using namespace std; 3  4 typedef long long LL; 5 const int maxn = 20020; 6 const int maxm = 100100; 7 int n, m; 8 int a[maxn]; 9 LL bit[maxm];10 LL c[maxm], d[maxm];11 12 inline int lowbit(int x) {13     return x & (-x);14 }15 16 void add(int i) {17     while(i <= m) {18         bit[i]++;19         i += lowbit(i);20     }21 }22 23 LL sum(int i) {24     LL ret = 0;25     while(i) {26         ret += bit[i];27         i -= lowbit(i);28     }29     return ret;30 }31 32 33 int main() {34     // freopen("in", "r", stdin);35     int T;36     scanf("%d", &T);37     while(T--) {38         scanf("%d", &n);39         m = -1;40         for(int i = 1; i <= n; i++) {41             scanf("%d", &a[i]);42             m = max(m, a[i]);43         }44         LL ret = 0;45         memset(bit, 0, sizeof(bit));46         for(int i = 1; i <= n; i++) {47             add(a[i]);48             c[i] = sum(a[i]-1);49         }50         memset(bit, 0, sizeof(bit));51         for(int i = n; i >= 1; i--) {52             add(a[i]);53             d[i] = sum(a[i]-1);54         }55         for(int i = 1; i <= n; i++) {56             ret += ((i - 1) - c[i]) * d[i] + (n - i - d[i]) * c[i];57         }58         cout << ret << endl;59     }60     return 0;61 }