# Untitled

Mar 16th, 2023
421
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3. #include <queue>
4. #include <cstring>
5. #include <algorithm>
6. #include <fstream>
7. using namespace std;
8. const int maxn = 1e6 + 5;
9. int segment_tree[3 * maxn];
10. void build_tree(int L, int R, int position) {
11.     if(L == R) {
12.         segment_tree[position] = 0;
13.     }
14.     else {
15.         int middle = (L + R) / 2;
16.         build_tree(L, middle, 2 * position);
17.         build_tree(middle + 1, R, 2 * position + 1);
18.         segment_tree[position] = segment_tree[2 * position] + segment_tree[2 * position + 1];
19.     }
20. }
21. int query(int L, int R, int position, int i, int j) {
22.     // L R i L R j L R
23.     if(i <= L and R <= j) {
24.         return segment_tree[position];
25.     }
26.     if(L > j or R < i) {
27.         return 0;
28.     }
29.     int middle = (L + R) / 2;
30.     return query(L, middle, 2 * position, i, j) + query(middle + 1, R, 2 * position + 1, i, j);
31. }
32. void update(int L, int R, int position, int idx) {
33.     if(L == R) {
34.         segment_tree[position] = 1;
35.         return;
36.     }
37.     int middle = (L + R) / 2;
38.     if(idx <= middle) {
39.         update(L, middle, 2 * position, idx);
40.     }
41.     else {
42.         update(middle + 1, R, 2 * position + 1, idx);
43.     }
44.     segment_tree[position] = segment_tree[2 * position] + segment_tree[2 * position + 1];
45. }
46. int main() {
47.     ios_base::sync_with_stdio(false);
48.     int n;
49.     cin >> n;
50.
51.     vector<int> v(n);
52.     for(int i = 0; i < n; i++) {
53.         cin >> v[i];
54.     }
55.     build_tree(0, n, 1);
56.     long long result = 0;
57.     for(int i = n - 1; i >= 0; i--) {
58.         update(0, n, 1, v[i]);
59.         result += query(0, n, 1, 0, v[i] - 1);
60.     }
61.     cout << result << endl;
62.     return 0;
63. }
64.