1.题目描述：点击打开链接
2.解题思路：根据题意，考虑第i个人当裁判的情况，假设第1个人到第i-1个人中，有num1个人的经验值小于A[i]，那么就有i-1-num1个人的经验值大于A[i]；同理，假设第i+1个人到第n个人之见有num2个人的经验值小于A[i]，那么就有n-i-num2个人的经验值大于A[i]。因此，根据乘法原理，第i个人当裁判时有num1*（i-1-num1)+num2*(n-i-num2)种比赛。最后累加即可。
然而如何计算这里的num1，num2呢？不难发现，，从左到右扫描第i个人，把A[i]当做C数组中的下标，假设有另外一个数组x，x[A[i]]表示前i-1个人中有多少人的经验值等于A[i]。那么num1就是前缀和x[1]+x[2]+…+x[A[i]-1]。统计完num1后，再令x[j]++即可，而这正是BIT的标准用法！同理可以逆序扫描，计算出num2。不过这里我们不需要额外开一个x数组，只需要C数组即可，引入数组x只是便于理解而已。从上面的叙述也可以看出，计算前缀和时应该把A[i]当做C数组中的“下标”看待。
本题还有一个技巧：为了便于管理第i个人当裁判时的比赛种类数目，用一个结构体来分别记录前i-1个人中经验值小于A[i]的人数lmin,大于的人数lmax；用rmin,rmax分别表示后n-i个人中经验值小于，大于A[i]的人数。便于随后累加结果。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;typedef long long LL;#define N 100000+10#define M 20000+10int C[N];int A[M];struct node{int lmax, lmin;int rmax, rmin;}f[M];int lowbit(int x){return x&-x;}int sum(int x)//这里的x要理解为C数组的下标{int ret = 0;while (x > 0){ret += C[x];x -= lowbit(x);}return ret;}void add(int x, int d)//x的理解同上{while (x <= N){C[x] += d;x += lowbit(x);}}int main(){freopen("t.txt", "r", stdin);int T;scanf("%d", &T);while (T–){int n;scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d", A + i);memset(C, 0, sizeof(C));for (int i = 1; i <= n; i++)//第i个人当裁判时，考虑前i-1个人{int num = sum(A[i]);//计算前i-1个人中有多少人的经验经验值小于A[i]f[i].lmin = num;f[i].lmax = i – 1 – num;add(A[i], 1);//更新C[i]}memset(C, 0, sizeof(C));for (int i = n; i >= 1; i–)//第i个人当裁判时，考虑后n-i个人{int num = sum(A[i]);//计算后n-i个人中有多少人的经验值小于A[i]f[i].rmin = num;f[i].rmax = n – i – num;add(A[i], 1);//更新C[i]}LL ans = 0;for (int i = 1; i <= n; i++)ans += (LL)f[i].lmax*f[i].rmin + (LL)f[i].lmin*f[i].rmax;printf("%lld\n", ans);}return 0;}
挫折其实就是迈向成功所应缴的学费。
