Given a number sequence which has N element(s), please calculate the number of different collocation for three number Ai, Aj, Ak, which satisfy that Ai < Aj > Ak and i < j < k.
Input
The first line is an integer N (N <= 50000). The second line contains N integer(s): A1, A2, ..., An(0 <= Ai <= 32768).
Output
There is only one number, which is the the number of different collocation.
Sample Input
5 1 2 3 4 1Sample Output
6 简单的一维树状数组统计 题目大意： 给出一列数，按输入顺序统计，取取其中任一数，存在一个在它之前输入且比它小的数，一个在它之后输入且比它小的数，构成一种组合 ，求组合的总数。 分析： 题目的数据域是32768，输入量是50000，显然，顺序统计比某一输入数小的数与比它大的数构成的组合总数必然会超时（O(n2)级）。 考虑输入与统计类问题，可以选用树状数组存储比某数小的数，从头至尾扫描一遍，再反序扫描一遍，可以得到左边与右边比该数小的数 的总数，相乘即可得到欲求结果，效率是O(nlogn)。 实现： 在输入过程中，每输入一个数，统计在它之前输入的数中比它小的（通过树状数组的求和方法），再将它的统计次数加一。再反序扫描， 将树状统计在实现一遍，此时将前面保存的统计数与后序统计数相乘加和即可。 代码： #include <cstdio> #include <memory> #define lowbit(w) (w & (-w)) #define MAX 32769 #define MAXN 50001 int C[MAX]; int left[MAXN], // 存储左边小于当前数的数量 num[MAXN]; int n; long long sum; // 考虑结果范围，此处用64位整数 void Modify(int x) { while (x < MAX) { C[x] ++; x += lowbit(x); } } int Sum(int x) { int sum = 0; while (x > 0) { sum += C[x]; x -= lowbit(x); } return sum; } int main() { while (scanf("%d", &n) != EOF) { sum = 0; memset(C, 0, sizeof(C)); // 顺序统计 for (int i = 1; i <= n; i++) { scanf("%d", &num[i]); left[i] = Sum(num[i] - 1); Modify(num[i]); } // 逆序统计 memset(C, 0, sizeof(C)); for (int i = n; i >= 1; i--) { sum += Sum(num[i] - 1) * left[i]; Modify(num[i]); } printf("%lld/n", sum); } return 0; }
