HDU_2492

    由于N比较大，枚举两个队员并计算其中有多少个裁判是行不通的，不妨换一种思路去枚举裁判，这样对于任意一个裁判而言，不同的比赛场数等于左边小于裁判skill rank的人数乘以右边大于裁判skill rank的人数，再加上右边小于裁判skill rank的人数乘以左边大于裁判skill rank的人数。

    在计算人数的时候，可以维护记录分别记录左右两边各个skill rank的人数的两棵线段树，每当枚举一个裁判时，先将裁判从右边的线段树删去，计算完之后再将裁判添加到左边的线段树中。

#include
     
       #include
      
        #define MAXD 400010 int N, M, a[MAXD], lt[MAXD], rt[MAXD]; void init() {
   int i, j, k;     memset(lt, 0, sizeof(lt));     memset(rt, 0, sizeof(rt));     scanf("%d", &N); for(i = 0; i < N; i ++)     {
           scanf("%d", &a[i]);         rt[a[i] + M] = 1;     } for(i = M - 1; i > 0; i --)         rt[i] = rt[2 * i] + rt[2 * i + 1]; } void updatel(int i) {
   for(; i ^ 1; i >>= 1)         lt[i >> 1] = lt[i] + lt[i ^ 1]; } void updater(int i) {
   for(; i ^ 1; i >>= 1)         rt[i >> 1] = rt[i] + rt[i ^ 1]; } int countl(int x, int y) {
   int i = M + x - 1, j = M + y + 1, ans = 0; for(; i ^ j ^ 1; i >>= 1, j >>= 1)     {
   if(~i & 1)             ans += lt[i ^ 1]; if(j & 1)             ans += lt[j ^ 1];     } return ans; } int countr(int x, int y) {
   int i = M + x - 1, j = M + y + 1, ans = 0; for(; i ^ j ^ 1; i >>= 1, j >>= 1)     {
   if(~i & 1)             ans += rt[i ^ 1]; if(j & 1)             ans += rt[j ^ 1];     } return ans; } void solve() {
   int i, j, k, t1, t2; long long int ans = 0; for(i = 0; i < N; i ++)     {
           t1 = t2 = 0;         rt[M + a[i]] = 0;         updater(M + a[i]);         t1 = countl(1, a[i]), t2 = countr(a[i], 100000);         ans = (long long int)t1 * t2 + ans;         t1 = countl(a[i], 100000), t2 = countr(1, a[i]);         ans = (long long int)t1 * t2 + ans;         lt[M + a[i]] = 1;         updatel(M + a[i]);     }     printf("%I64d\n", ans); } int main() {
   int t; for(M = 1; M < 100002; M <<= 1);     scanf("%d", &t); while(t --)     {
           init();         solve();     } return 0; }