Advertisement
Josif_tepe

Untitled

Oct 5th, 2023
906
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.36 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 = 100005;
  16. const ll INF = 3e16 + 10;
  17.  
  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.     vector<int> v(n);
  60.     vector<pair<int, int> > cords;
  61.     for(int i = 0; i < n; i++) {
  62.         cin >> v[i];
  63.         cords.push_back(make_pair(v[i], i));
  64.     }
  65.     sort(cords.begin(), cords.end());
  66.     vector<int> compressed;
  67.     for(int i = 0; i < n; i++) {
  68.         compressed.push_back(cords[i].second);
  69.     }
  70.    
  71.     build_tree(0, n, 1);
  72.     vector<ll> right_smaller(n);
  73.     for(int i = n - 1; i >= 0; i--) {
  74.         update(0, n, 1, compressed[i], 1);
  75.         right_smaller[i] = query(0, n, 1, 0, compressed[i] - 1);
  76.     }
  77.     vector<ll> left_bigger(n);
  78.     build_tree(0, n, 1);
  79.     for(int i = 0; i < n; i++) {
  80.         update(0, n, 1, compressed[i], 1);
  81.         left_bigger[i] = query(0, n, 1, compressed[i] + 1, n);
  82.     }
  83.    
  84.     ll res = 0;
  85.     for(int i = 0; i < n; i++) {
  86.         res += right_smaller[i] * left_bigger[i];
  87.     }
  88.     cout << res << endl;
  89.  
  90.     return 0;
  91. }
  92.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement