此題是求一個(gè)數(shù)字序列中，長度為3的子序列(a,b,c)，且滿足條件a<=b<=c或者c<=b<=a的子序列的個(gè)數(shù)。
明顯枚舉每個(gè)b，求每個(gè)b左邊的a的個(gè)數(shù)和右邊c的個(gè)數(shù)，以及左邊c的個(gè)數(shù)和右邊a的個(gè)數(shù)，然后累加左右乘積求和即可。
剛開始只求了滿足條件a<=b<=c的部分，而且忘記用64位了。wa了幾次。求左邊a的個(gè)數(shù)其實(shí)就是求小于等于b的數(shù)字
的個(gè)數(shù)，這個(gè)剛好可以用樹狀數(shù)組或者線段樹求。具體見代碼。
代碼如下：
#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;
}