题意：
给出序列 A，
求满足 a<b,c<d, A[a] < A[b] , A[c] > A[d] 的互不相同的 (a,b,c,d) 的对数
分析：
a<b, A[a] < A[b] 为顺序对， c<d, A[c] > A[d] 为逆序对
故先求出所有顺序对和逆序对的乘积，再减去重复的，即四个数中有任意两个相等的情况
重复的有以下四种:
a == c b,d > a,c
b == d a,c < b,d
b == c a < b,c < d
a == d c < a,d < b
故对于每个 i ，答案均要减去这四种重复的
顺逆序对可用树状数组求
首先要离散化，再要考虑有相同数字的情况
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 const int MAXN = 50005; 7 int c[MAXN], top; 8 void modify(int x,int num) 9 { 10 while (x <= top) c[x] += num, x += x&-x; 11 } 12 int query(int x) 13 { 14 int s = 0; 15 while (x > 0) s+= c[x], x -= x&-x; 16 return s; 17 } 18 int n; 19 int a[MAXN], b[MAXN]; 20 struct Node 21 { 22 long long preS, preL, subS, subL;//pre smaller , pre larger , sub smaller , sub larger 23 }s[MAXN]; 24 long long ans, sumL, sumS;//逆序对，顺序对 25 void Init() 26 { 27 for (int i = 0; i < n; i++) b[i] = a[i]; 28 sort(b, b + n); 29 int size = unique(b,b+n) - b; 30 sumL = sumS = top = 0; 31 for (int i = 0; i < n; i++)//离散化 32 { 33 a[i] = lower_bound(b,b+size,a[i]) - b + 1; 34 top = max(top, a[i]); 35 } 36 memset(c, 0, sizeof(c)); 37 for (int i = 0; i < n; i++) 38 { 39 s[i].preS = query(a[i] - 1); 40 s[i].preL = i - query(a[i]); 41 sumL += s[i].preL; 42 sumS += s[i].preS; 43 modify(a[i], 1); 44 } 45 memset(c, 0, sizeof(c)); 46 for (int i = n-1; i >= 0; i--) 47 { 48 s[i].subS = query(a[i] - 1); 49 s[i].subL = (n-1 - i) - query(a[i]); 50 modify(a[i], 1); 51 } 52 } 53 int main() 54 { 55 while(~scanf("%d", &n)) 56 { 57 for (int i = 0; i < n; i++) 58 scanf("%d", &a[i]); 59 Init(); 60 ans = sumL * sumS ; 61 for (int i = 0; i < n; i++) 62 { 63 ans -= s[i].subL * s[i].subS;// a == c b,d > a,c 64 ans -= s[i].preL * s[i].preS;// b == d a,c < b,d 65 ans -= s[i].subS * s[i].preS;// b == c a < b,c < d 66 ans -= s[i].preL * s[i].subL;// a == d c < a,d < b 67 } 68 printf("%I64d ", ans); 69 } 70 }