题目解析 购买股票赚钱的方案条件为 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)。

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

#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) {} }; 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; }

#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) {} }; 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; }