思路

步骤一：第一棵树状数组，先把“两种情况的总和”都算出来

• 对每个位置 $i$，设

  • $cnt_i$ 表示从 $i$ 开始向右数，所有满足 $a_k < a_i$ 的元素个数，其中 $k > i$。

• 则以 $i$ 为左端点，右侧所有值 $<a_i$ 的二元组 $(j,k)$（$j<k$）总数为

  • $\binom{cnt_i}{2}$

题目内容

对于给定的由$n$个整数组成的数组{$a_1,a_2,...,a_n$}，计算其中有多少个三元组$(i,j,k)$满足$1≤i<j<k≦n$且$a_i>a_k>a_j$。例如，在数组{$4,1,2,3$}中三元组$(1,2,3),(1,2,4),(1,3,4)$都是满足条件的三元组。更具体地，计算:

$\sum_{1≤i＜j＜k≤n}[a_i＞a_k＞a_j]$