hdu 2492 Ping pong

此題是求一個數字序列中，長度為3的子序列(a,b,c)，且滿足條件a<=b<=c或者c<=b<=a的子序列的個數。
   明顯枚舉每個b，求每個b左邊的a的個數和右邊c的個數，以及左邊c的個數和右邊a的個數，然後累加左右乘積求和即可。
   剛開始只求了滿足條件a<=b<=c的部分，而且忘記用64位了。wa了幾次。求左邊a的個數其實就是求小於等於b的數字
的個數，這個剛好可以用樹狀數組或者線段樹求。具體見代碼。

   代碼如下：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long INT;
const INT MAX_N =  100010;
const INT N = 20010;
INT nN;
INT nNum[N];
INT nTree[MAX_N + 10];
INT nLeft[2][N], nRight[2][N];

INT LowBit(INT nI)
{
    return nI & (-nI);
}

void Add(INT nI, INT nAdd)
{
    while (nI <= MAX_N)
    {
        nTree[nI] += nAdd;
        nI += LowBit(nI);
    }
}

INT Query(INT nPos)
{
    INT nAns = 0;
    while (nPos > 0)
    {
        nAns += nTree[nPos];
        nPos -= LowBit(nPos);
    }
    return nAns;
}

int main()
{
    INT nT;
   
    scanf("%I64d", &nT);
    while (nT--)
    {
        scanf("%I64d", &nN);
        memset(nTree, 0, sizeof(nTree));
        for (INT i = 1; i <= nN; ++i)
        {
            scanf("%I64d", &nNum[i]);
            nLeft[0][i] = Query(nNum[i]);
            nLeft[1][i] = Query(MAX_N) - Query(nNum[i] - 1);
            Add(nNum[i], 1);
        }
        memset(nTree, 0, sizeof(nTree));
        for (INT i = nN; i >= 1; --i)
        {
            nRight[0][i] = Query(MAX_N) - Query(nNum[i] - 1);
            nRight[1][i] = Query(nNum[i]);
            Add(nNum[i], 1);
        }
        INT nAns = 0;
        for (INT i = 1; i <= nN; ++i)
        {
            nAns += nLeft[0][i] * nRight[0][i] + nLeft[1][i] * nRight[1][i];
        }
        printf("%I64d\n", nAns);
    }
   
    return 0;
}