mickypinata

FORCE-T0459D: Pashmak and Parmida's Problem

Nov 10th, 2021 (edited)
698
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long lli;
  5. typedef pair<int, int> pii;
  6.  
  7. const int N = 1e6;
  8.  
  9. vector<pii> newArr;
  10. int arr[N + 1], fi[N + 1], fj[N + 1];
  11.  
  12. lli ans = 0;
  13. int mergeSort(vector<pii> &v, int l, int r){
  14.     if(l == r){
  15.         return v[l].second;
  16.     }
  17.     int m = (l + r) / 2;
  18.     int cntLeft = mergeSort(v, l, m);
  19.     int cntRight = mergeSort(v, m + 1, r);
  20.     int cnt = cntRight;
  21.     pii tmp[r - l + 1];
  22.     int i = l;
  23.     int j = m + 1;
  24.     int k = 0;
  25.     while(i <= m && j <= r){
  26.         if(v[i].first > v[j].first){
  27.             tmp[k++] = v[i];
  28.             if(v[i].second == 0){
  29.                 ans += cnt;
  30.             }
  31.             ++i;
  32.         } else {
  33.             tmp[k++] = v[j];
  34.             if(v[j].second == 1){
  35.                 --cnt;
  36.             }
  37.             ++j;
  38.         }
  39.     }
  40.     while(i <= m){
  41.         tmp[k++] = v[i++];
  42.     }
  43.     while(j <= r){
  44.         tmp[k++] = v[j++];
  45.     }
  46.     for(int i = l; i <= r; ++i){
  47.         v[i] = tmp[i - l];
  48.     }
  49.     return cntLeft + cntRight;
  50. }
  51.  
  52. int main(){
  53.  
  54.     int n;
  55.     scanf("%d", &n);
  56.     for(int i = 1; i <= n; ++i){
  57.         scanf("%d", &arr[i]);
  58.     }
  59.     map<int, int> mp;
  60.     for(int i = 1; i <= n; ++i){
  61.         ++mp[arr[i]];
  62.         fi[i] = mp[arr[i]];
  63.     }
  64.     mp.clear();
  65.     for(int i = n; i >= 1; --i){
  66.         ++mp[arr[i]];
  67.         fj[i] = mp[arr[i]];
  68.     }
  69.     for(int i = 1; i <= n; ++i){
  70.         newArr.emplace_back(fj[i], 1);
  71.         newArr.emplace_back(fi[i], 0);
  72.     }
  73.     mergeSort(newArr, 0, (int)newArr.size() - 1);
  74.     cout << ans;
  75.  
  76.     return 0;
  77. }
  78.  
  79. // Fenwick Solution
  80. #include <bits/stdc++.h>
  81. using namespace std;
  82.  
  83. typedef long long lli;
  84.  
  85. const int N = 1e6;
  86. const int logN = log2(N);
  87.  
  88. map<int, int> mp;
  89. int arr[N + 1], fi[N + 1], fj[N + 1], fw[N + 1], n;
  90.  
  91. void fwUpdate(int i, int x){
  92.     for(; i <= n; i += (i & -i)){
  93.         fw[i] += x;
  94.     }
  95. }
  96.  
  97. int fwQuery(int i){
  98.     int sum = 0;
  99.     for(; i >= 1; i -= (i & -i)){
  100.         sum += fw[i];
  101.     }
  102.     return sum;
  103. }
  104.  
  105. int main(){
  106.  
  107.     scanf("%d", &n);
  108.     for(int i = 1; i <= n; ++i){
  109.         scanf("%d", &arr[i]);
  110.         ++mp[arr[i]];
  111.         fi[i] = mp[arr[i]];
  112.     }
  113.     mp.clear();
  114.     lli ans = 0;
  115.     for(int i = n; i >= 1; --i){
  116.         ++mp[arr[i]];
  117.         fj[i] = mp[arr[i]];
  118.         ans += fwQuery(fi[i] - 1);
  119.         fwUpdate(fj[i], 1);
  120.     }
  121.     cout << ans;
  122.  
  123.     return 0;
  124. }
  125.  
RAW Paste Data Copied