学步园

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2492

代码风格：www.notonlysuccess.com

题目大意：求有多少组数满足：( i < j < k 并且 ai < aj < ak) ||( i > j > k 并且 ai < aj < ak)

算法：线段树

思路：presm[i] = 前面有多少个数字比a[i]小，endbig[i]后面有多少个数字比a[i]大；prebig[i] = 前面有多少个数字比a[i]大，endsm[i]后面有多少个数字比a[i]小；公式： sum = ∑（presm[i] * endbig[i]+prebig[i] * endsm[i]）（1 < i < n）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

#define lson l, m, rt << 1
#define rson m+1, r, rt << 1 | 1
#define mid int m = (l+r) >> 1

const int Max = 100000;
int a[565656];
int w[898989];
int cnt[498989];

void update(int d, int l, int r, int rt)
{
    cnt[rt] ++;
    if(l == r)
        return ;
     mid ;
     if(d <= m)
         update(d, lson);
     else
         update(d, rson);
}

int query(int k, int l, int r, int rt)
{
    if(l == r)
        return cnt[rt];
    mid ;
    if(k <= m)
        return query(k, lson);
    else{
        int ret = query(k, rson);
        return ret + cnt[rt << 1];
    }

}

int bin(int key, int n)
{
    int l = 1, r = n;
    while(l <= r)
    {
        mid ;
        if(key == w[m])
            return m;
        if(key < w[m])
            r = m-1;
        else
            l = m+1;
    }
    return -1;
}

int main()
{
    int n, T;
    scanf("%d", &T);
    while(T -- )
    {
        scanf("%d", &n);
        __int64 ans = 0;
        memset(cnt, 0, sizeof(cnt));
        int i;
        for(i = 1; i <=  n; i ++)
        {
            scanf("%d", &a[i]);
            w[i] = a[i];
        }
        sort(w+1, w+n+1);
        for(i = 1; i <= n; i ++)
        {
            int xx = bin(a[i], n);
            int k = query(a[i], 1, Max, 1);//pre比他小的
            int m = xx - 1 - k;//后面比他小的
            int u = (n-i) - m;//后面比他大的
            int v = i - 1 - k;//前面比他大的
            update(a[i], 1, Max, 1);
            ans += (__int64)k * (__int64)u + (__int64)v * (__int64)m;
        }
        printf("%I64d\n", ans);
    }
    return 0;
}