Advertisement
Josif_tepe

Untitled

Mar 22nd, 2024
810
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.79 KB | None | 0 0
  1. #include <queue>
  2. #include <iostream>
  3. #include <vector>
  4. #include <cstring>
  5. #include <iostream>
  6. #include <set>
  7. #include <cstring>
  8. #include <stack>
  9. #include <algorithm>
  10. #include <map>
  11. #include <cmath>
  12. //#include <bits/stdc++.h>
  13. using namespace std;
  14. typedef long long ll;
  15. const int maxn = 1e6 + 10;
  16. const ll INF = 3e16 + 10;
  17. const int max_point = 10000000;
  18. int segment_tree[3 * maxn];
  19. void build_tree(int L, int R, int node) {
  20.     if(L == R) {
  21.         segment_tree[node] = 0;
  22.     }
  23.     else {
  24.         int mid = (L + R) / 2;
  25.         build_tree(L, mid, 2 * node);
  26.         build_tree(mid + 1, R, 2 * node + 1);
  27.         segment_tree[node] = segment_tree[2 * node] + segment_tree[2 * node + 1];
  28.     }
  29. }
  30. void update(int L, int R, int node, int idx, int new_value) {
  31.     if(L == R) {
  32.         segment_tree[node] = new_value;
  33.         return;
  34.     }
  35.     int mid = (L + R) / 2;
  36.     if(idx <= mid) {
  37.         update(L, mid, 2 * node, idx, new_value);
  38.     }
  39.     else {
  40.         update(mid + 1, R, 2 * node + 1, idx, new_value);
  41.     }
  42.     segment_tree[node] = segment_tree[2 * node] + segment_tree[2 * node + 1];
  43. }
  44. int query(int L, int R, int node, int i, int j) {
  45.     // L R i L R j L R
  46.     if(i <= L and R <= j) {
  47.         return segment_tree[node];
  48.     }
  49.     if(R < i or j < L) {
  50.         return 0;
  51.     }
  52.     int mid = (L + R) / 2;
  53.     return query(L, mid, 2 * node, i, j) + query(mid + 1, R, 2 * node + 1, i, j);
  54. }
  55. int main() {
  56.     ios_base::sync_with_stdio(false);
  57.     int n;
  58.     cin >> n;
  59.     build_tree(0, n, 1);
  60.     vector<int> v(n);
  61.     for(int i = 0; i < n; i++) {
  62.         cin >> v[i];
  63.     }
  64.      
  65.     ll res = 0;
  66.     for(int i = n - 1; i >= 0; i--) {
  67.         update(0, n, 1, v[i], 1);
  68.         res += query(0, n, 1, 0, v[i] - 1);
  69.     }
  70.     cout << res << endl;
  71.     return 0;
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement