题目传送门
这道题与树状数组求逆序对的思路有些近似，是一道树状数组求前缀的基础题目。
我们枚举第i个人当裁判的话，假设a1到a[i-1]中有ci个比ai小，那么就有(i-1)-ci个比ai大，同理，假设a[i+1]到an中有di个比ai小，那么就有(n-i)-di个比ai大，然后根据乘法原理和加法原理，i当裁判有ci(n-i-di)+(i-ci-1)*di，这样问题就转化为求c,d的值
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<set> #include<queue> #include<algorithm> #include<vector> #include<cstdlib> #include<cmath> #include<ctime> #include<stack> #define rez(i,x,y) for(int i=x;i>=y;i--) #define res(i,x,y) for(int i=x;i<=y;i++) #define INF 2100000000 #define ll long long #define clr(x) memset(x,0,sizeof(x)) using namespace std; const int egn = 100005; const int maxn = 100000 + 50; int Ti,n; int num[maxn],x[maxn],c[maxn],d[maxn]; template<class T> inline void readin(T &res){ static char ch; while((ch=getchar())<'0'||ch>'9'); res=ch-48; while((ch=getchar())<='9'&&ch>='0') res=res*10+ch-48; } int lowbit(int x){return (x&(-x));} int sum(int x){ int ret=0; while(x>0) ret+=num[x],x-=lowbit(x); return ret; } void add(int x){ while(x<egn) ++num[x],x+=lowbit(x); } int main(){ readin(Ti); while(Ti--){ clr(x),clr(c),clr(d); readin(n); ll tot=0; for(int i=1;i<=n;i++) readin(x[i]); clr(num); for(int i=1;i<=n;i++){ c[i]=sum(x[i]); add(x[i]); } clr(num); for(int i=n;i>=1;i--){ d[i]=sum(x[i]); add(x[i]); } for(int i=1;i<=n;i++){ tot+=((ll)c[i]*(n-i-d[i])+(ll)d[i]*(i-c[i]-1)); } cout<<tot<<endl; } return 0; }