题目解析 购买股票赚钱的方案条件为 a[i]<a[j](1≤i<j≤n)a[i] < a[j](1 \le i < j \le n)a[i]<a[j](1≤i<j≤n)。 令 cnt[i]=∑j=1i−1xj(2≤i≤n)cnt[i] = \sum_{j=1}^{i-1} x_j (2 \le i \le n)cnt[i]=∑j=1i−1 xj (2≤i≤n)，其中若 a[j]<a[i]a[j] < a[i]a[j]<a[i]，xj=1x_j = 1xj =1 否则为 000。 我们可以利用 树状数组\bf{树状数组}树状数组 或者 平衡树\bf{平衡树}平衡树 来高效统计 cnt[i]cnt[i]cnt[i]。 从前至后遍历数组，从树状数组或者平衡树中查询小于 a[i]a[i]a[i] 的元素数量，然后将 a[i]a[i]a[i] 插入树状数组或者平衡树中。 AC代码 复杂度分析 树状数组完成插入和查询操作的时间复杂度均为 O(log⁡n)O(\log{n})O(logn)。 总时间复杂度 O(nlog⁡n)O(n\log{n})O(nlogn)。

额好像把数组倒过来求逆序对也行（？ 或者小小改个符号？