Advertisement
Josif_tepe

Untitled

Sep 21st, 2023
902
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.18 KB | None | 0 0
  1. #include <queue>
  2. #include <iostream>
  3. #include <vector>
  4. #include <cstring>
  5. #include <iostream>
  6. //#include <bits/stdc++.h>
  7. using namespace std;
  8. typedef long long ll;
  9. const int maxn = 1e6 + 10;
  10. int segment_tree[maxn];
  11.  
  12. void build(int node, int L, int R) {
  13.     if(L == R) {
  14.         segment_tree[node] = 0;
  15.     }
  16.     else {
  17.         int mid = (L + R) / 2;
  18.         build(2 * node, L, mid);
  19.         build(2 * node + 1, mid + 1, R);
  20.         segment_tree[node] = segment_tree[2 * node] + segment_tree[2 * node + 1];
  21.     }
  22. }
  23. int query(int node, int L, int R, int i, int j) {
  24.     // L R i L R j L R
  25.     if(i <= L and R <= j) {
  26.         return segment_tree[node];
  27.     }
  28.     if(R < i or j < L) {
  29.         return 0;
  30.     }
  31.     int mid = (L + R) / 2;
  32.     return query(2 * node, L, mid, i, j) + query(2 * node + 1, mid + 1, R, i, j);
  33. }
  34. void update(int node, int L, int R, int idx) {
  35.     if(L == R) {
  36.         segment_tree[node] += 1;
  37.         return;
  38.     }
  39.     int mid = (L + R) / 2;
  40.     if(idx <= mid) {
  41.         update(2 * node, L, mid, idx);
  42.     }
  43.     else {
  44.         update(2 * node + 1, mid + 1, R, idx);
  45.     }
  46.     segment_tree[node] = segment_tree[2 * node] + segment_tree[2 * node + 1];
  47. }
  48. int main() {
  49.     ios_base::sync_with_stdio(false);
  50.     int n;
  51.     cin >> n;
  52.     vector<int> v(n);
  53.     vector<pair<int, int> > compressed;
  54.     for(int i = 0; i < n; i++) {
  55.         cin >> v[i];
  56.         compressed.push_back(make_pair(v[i], i));
  57.     }
  58.     sort(compressed.begin(), compressed.end());
  59.     vector<int> tmp;
  60.     for(int i = 0; i < n; i++) {
  61.         tmp.push_back(compressed[i].second);
  62.     }
  63.     reverse(tmp.begin(), tmp.end());
  64.     build(1, 0, n);
  65.     vector<ll> smaller;
  66.     for(int i = 0; i < n; i++) {
  67.         update(1, 0, n, tmp[i]);
  68.         smaller.push_back(query(1, 0, n, 0, tmp[i] - 1));
  69.     }
  70.     build(1, 0, n);
  71.     vector<ll> bigger;
  72.     for(int i = n - 1; i >= 0; i--) {
  73.         update(1, 0, n, tmp[i]);
  74.         bigger.push_back(query(1, 0, n, tmp[i] + 1, n));
  75.     }
  76.     reverse(bigger.begin(), bigger.end());
  77.    
  78.     ll res = 0;
  79.     for(int i = 0; i < n; i++) {
  80.         res += bigger[i] * smaller[i];
  81.     }
  82.     cout << res << endl;
  83.     return 0;
  84. }
  85.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement