离散化一下(1---n),当插入第i个人时(这个人视作裁判, i从0开始), 假设这个人插入的位置为j,设 t=sum(j) 则
1. 在i之前更新的,值比i小的人数为 t个
2. 在i之后更新的,值比i小的人数为(i-t)个
3. 在i之前更新的,值比i大的人数为(n-i-j+t)个
4. 在i之后更新的,值比i大的人数为(j-1-t)个
所以对于每个i,则有ans += (LL)t*(n-i-j+t) + (LL)(i-t)*(j-1-t);
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define maxn 20003 #define LL long long int n, c[maxn], a[maxn], b[maxn]; void add(int x, int v) { while(x <= n) { c[x] += v; x += x & -x; } } int sum(int x) { int s = 0; while(x > 0) { s += c[x]; x -= x & -x; } return s; } int main() { int i, j, cas; scanf("%d", &cas); while(cas--) { scanf("%d", &n); memset(c, 0, sizeof(int)*(n+1)); for(i = 0; i < n; i++) scanf("%d", &a[i]), b[i] = a[i]; sort(b, b+n); LL ans = 0; for(i = 0; i < n; i++) { j = lower_bound(b, b+n,a[i])-b+1; int t = sum(j); ans += (LL)t *(n-i-j+t) + (LL)(i-t)*(j-1-t); //printf("t = %d ans = %I64d\n", t, ans); add(j, 1); } printf("%lld\n", ans); } return 0; }