题意：有n个数a1, a2, ..., an，问i < j < k且ai > aj > ak的三角对有多少对(3 <= n <= 10^6, 1 <= ai <= 10^9)。
题目链接：http://codeforces.com/problemset/problem/61/E
——>>对于一个位置j，其左边有L[j]个比aj大的数，其右边有R[j]个比aj小的数，那么，ai可从L[j]个数中取，ak可从R[j]个数中取，此时可组成L[j] * R[j]个三角对，枚举j的位置，求和。
由于数据量不小，2层for以O(n^2)找L与R已超过题目所允许的时间，这里恰恰可用树状数组来求得R，而L可根据R推出。
因为1 <= ai <= 10^9，数组开不下，但输入个数不超过10^6，所以可做一个重映射，使输入的数根据大小重映射为1到n，设重映射后的数组为f。
用树状数组求出R后，因为R[i]表示第i个数的右边有多少个比f[i]小的数，而第i个数的右边共有n-i个数，所以第i个数的右边有n - i - R[i]个比f[i]大的数，而整个f有n-f[i]个比f[i]大的数，所以第i个数的左边有n - f[i] - (n - i - R[i]) = R[i] - f[i] + i个比f[i]大的数，即L[i] = R[i] - f[i] + i。
#include <cstdio>
#include <algorithm>
#include <cstring>using namespace std;const int maxn = 1000000 + 10;
int n, f[maxn], C[maxn], L[maxn], R[maxn];struct node{int id;int val;bool operator < (const node& e) const{return val < e.val;}
}a[maxn];int lowerbit(int x){return x & (-x);
}void add(int x, int v){while(x <= n){C[x] += v;x += lowerbit(x);}
}int sum(int x){int ret = 0;while(x){ret += C[x];x -= lowerbit(x);}return ret;
}int main()
{int i;while(scanf("%d", &n) == 1){for(i = 1; i <= n; i++){scanf("%d", &a[i].val);a[i].id = i;}sort(a+1, a+1+n);for(i = 1; i <= n; i++) f[a[i].id] = i; //重映射memset(C, 0, sizeof(C));for(i = n; i >= 1; i--){R[i] = sum(f[i]);add(f[i], 1);}for(i = 1; i <= n; i++) L[i] = R[i] - f[i] + i;long long ret = 0;for(i = 2; i < n; i++) ret += (long long)L[i] * R[i];printf("%I64d\n", ret);}return 0;
}