?https://codeforces.com/contest/61/problem/E

題意:?

已知互不相同的整數(shù)序列a[1], a[2],..., a[n],? 求 i<j<k 且 a[i]>a[j]>a[k] 的三元組個(gè)數(shù)

思路：

如果只有2元組即是求逆序?qū)€(gè)數(shù)。

三元組的情形，先用一個(gè)樹狀數(shù)組x表示 大于a[i]且下標(biāo)小于i的數(shù)據(jù)個(gè)數(shù)

再把x中大于a[i]且下標(biāo)小于i的個(gè)數(shù)存入樹狀數(shù)組y中，存入位置為a[i]的順序標(biāo)號(hào)b0。

假設(shè) 樹狀數(shù)組y中大于順序標(biāo)號(hào)b的數(shù)據(jù)之和為y.sum(b)，設(shè)b<b0, 且b0數(shù)據(jù)的下標(biāo)小于b數(shù)據(jù)的下標(biāo)。

?而x.sum(b0)表示大于b0的數(shù)據(jù)個(gè)數(shù)， 且這些數(shù)據(jù)的下標(biāo)小于b0數(shù)據(jù)的下標(biāo)，

?所以，y.sum(b) 為 a[k]?>?a[i]?>?a[j] 的三元組個(gè)數(shù)，其中a[j]的順序標(biāo)號(hào)b。

input

5

1 20 10 8 3?