Advertisement
Josif_tepe

Untitled

Mar 16th, 2023
589
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.66 KB | None | 0 0
  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.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement