最大上升三元组数量

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

4
const int MAXN = 3e4+10;
5
typedef long long ll;
6

7
class MyTree {
8
public:
9
    vector<int> v;
10
    int sz;
11
    MyTree(int sz) {
12
        this->sz = sz;
13
        v.resize(sz + 1);
14
    }
15

16
    int lowbit(int x) {
17
        return x & (-x);
18
    }
19

20
    void add(int x, int value) {
21
        while (x <= sz) {
22
            v[x] += value;
23
            x += lowbit(x);
24
        }
25
    }
26

27
    int query(int x) {
28
        int sum = 0;
29
        while (x > 0) {
30
            sum += v[x];
31
            x -= lowbit(x);
32
        }
33
        return sum;
34
    }
35
};
36

37
MyTree f1(MAXN), f2(MAXN);
38

39
void solve() {
40
    int n;
41
    cin >> n;
42

43
    vector<ll> arr(n + 1);
44
    vector<ll> sorted_arr(n + 1);
45

46
    for (int i = 1; i <= n; i++) {
47
        cin >> arr[i];
48
        sorted_arr[i] = arr[i];  // 复制数组用于排序
49
    }
50

51
    sort(next(begin(sorted_arr)), end(sorted_arr)); // 仅排序副本
52
    auto f = [&](ll x) {
53
        return lower_bound(next(begin(sorted_arr)), end(sorted_arr), x) - sorted_arr.begin();
54
    };
55

56
    ll ans = 0;
57
    for (int i = 1; i <= n; i++) {
58
        int idx = f(arr[i]);
59
        f1.add(idx, 1);
60
        f2.add(idx, f1.query(idx - 1));  // 确保索引合法
61
        ans += f2.query(idx - 1);
62
    }
63
    cout << ans << endl;
64
}
65

66
int main() {
67
    ios_base::sync_with_stdio(false);
68
    cin.tie(NULL);
69
    cout.tie(NULL);
70

71
    solve();
72
    return 0;
73
}