题意：
给定1~n的一个排列 用A[]数组保存，问有多少下标(a,b,c,d)四元组满足：
a
解析：
题目中n的范围是50000，O（n^2) 复杂度肯定超时。那么这题明显考察的是log2(n)的算法，对于这题可以用线段树或者树状数组，同时要用到输入外挂，不然会超时。
思路（参考别人做法）
枚举c的位置，那么每一次枚举中的方法数为 1~c-1 中(a,b)的个数 乘以 c~n中（c,d)的个数。累加起来即为答案。
1~c-1中(a,b)的个数相当于枚举b的位置，然后计算出b前面有多少数比A[b]小，该值要保存下来，下一次枚举c的时候，该值再加上c-1前面有多少比a[c-1]小的数即为当前情况下1~c-1中(a,b)的个数，也就是b=c-1的时候，因为枚举b之前的情况已经算过了。
因为当算c时只是算出 比c小的方法数，这个只是满足比c小的二元组的个数。而c前面的二元组也要计算在内，所以要加上c前面的比c小的个数。
用树状数组来做。本题n范围50000，而且每个数都不相同很关键。所以我们就开辟n个位置，一开始每个位置都是0，其实每个位置不是0就是1，因为每个数只有一个。
比如 1 3 2 4 5
一开始 c数组 0 0 0 0 0
先统计，再输入，因为计算a[i]前面有多少比它小的数，不包括它自己，而树状数组计算和的时候，要包括它自己。
i=1，树状数组求和前缀和 pre[1]=0 ,
此时0 0 0 0 0， 输入1，变为 1 0 0 0 0
i=2，a[2]=3，要看 3前面有多少个数，也就是看c数组的3个位置前面有多少个1，1代表已经输入，
发现1 0 0 0 0前三个数只有一个1，也就是pre[2]=1 (输入的第二个数之前只有1个比它小的），输入3以后，c数组变为 1 0 1 0 0
i=3, a[3]= 2, 要看2前面有多少个数，也就是看c数组前2个位置前面有多少个1，发现10100前两个数中只有一个1，也就是pre[3]=1前缀和可以算出来，那么后缀和 = num2[i] = n-i-a[i]+num[i]+1;
AC代码
#include
#include
#include
#include
#include
using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const int N = 5e4 + 10; int n; ll C[N], a[N]; inline void read(ll &x) { int flag = 0; x = 0; char c = getchar(); if(c == '-') flag = 1; while(c < '0' || c > '9') { if(c == '-') flag = 1; c = getchar(); } while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); if(flag) x = -x; } inline int lowbit(int x) { return x & (-x); } int query(int x) { int ret = 0; while(x > 0) { ret += C[x]; x -= lowbit(x); } return ret; } void add(int x, int d) { while(x <= n) { C[x] += d; x += lowbit(x); } } int num[N] , num2[N]; int main() { int T; scanf("%d", &T); while(T--) { ll ans = 0, pre = 0; scanf("%d", &n); memset(C, 0, sizeof(C)); for(int i = 1; i <= n; i++) { read(a[i]); num[i] = query(a[i]); //计算a[i]之前比a[i]小的数字 num2[i] = n-i-a[i]+num[i]+1; //计算a[i]之后比a[i]大的数字 add(a[i], 1); ans += pre * num2[i]; pre += num[i]; } printf("%lld\n", ans); } return 0; }