正经题解｜股票购买方案数

题目解析

购买股票赚钱的方案条件为 $a[i] < a[j](1 \le i < j \le n)$。

令 $cnt[i] = \sum_{j=1}^{i-1} x_j (2 \le i \le n)$，其中若 $a[j] < a[i]$，$x_j = 1$ 否则为 $0$。

我们可以利用 $\bf{树状数组}$ 或者 $\bf{平衡树}$ 来高效统计 $cnt[i]$。

从前至后遍历数组，从树状数组或者平衡树中查询小于 $a[i]$ 的元素数量，然后将 $a[i]$ 插入树状数组或者平衡树中。

AC代码

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

constexpr int N = 5e5;

template<class T>
class FenwickTree {
private:
    int n;
    vector<T> sum;
    int lowbit(int x) {return x & -x;}
public:
    FenwickTree(int n = 0) : n(n), sum(n + 1) {}
 
    void add(int x, T d) {
        for (; x <= n; x += lowbit(x))
            sum[x] += d;
    }

    T ask(int x) {
        T res = 0;
        for (; x; x -= lowbit(x))
            res += sum[x];
        return res;
    }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    FenwickTree<int> cnt(N);
    int n; cin >> n;
    i64 res = 0;
    for (int i = 1; i <= n; ++i) {
        int x; cin >> x;
        res += cnt.ask(x - 1);
        cnt.add(x, 1);
    }
    cout << res << '\n';
    return 0;
}

复杂度分析

树状数组完成插入和查询操作的时间复杂度均为 $O(\log{n})$。
总时间复杂度 $O(n\log{n})$。