Advertisement
Josif_tepe

Untitled

Mar 12th, 2023
707
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.64 KB | None | 0 0
  1. #include <iostream>
  2. #include <map>
  3. #include <cmath>
  4. #include <set>
  5. #include <vector>
  6. using namespace std;
  7. typedef long long ll;
  8. const int maxn = 1e6 + 5;
  9. int segment_tree[3 * maxn];
  10. void build(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(L, middle, 2 * position);
  17.         build(middle + 1, R, 2 * position + 1);
  18.         segment_tree[position] = segment_tree[2 * position] + segment_tree[2 * position + 1];
  19.     }
  20. }
  21. // L R i L R j L R
  22. int query(int L, int R, int position, int i, int j) {
  23.     if(i <= L and R <= j) {
  24.         return segment_tree[position];
  25.     }
  26.     if(R < i or j < L) {
  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.     build(0, n, 1);
  52.     vector<int> v(n);
  53.     for(int i = 0; i < n; i++) {
  54.         cin >> v[i];
  55.     }
  56.     ll inversions = 0;
  57.     for(int i = n - 1; i >= 0; i--) {
  58.         inversions += query(0, n, 1, 0, v[i] - 1);
  59.         update(0, n, 1, v[i]);
  60.     }
  61.     cout << inversions << endl;
  62.     return 0;
  63. }
  64.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement