FORCE-T0459D: Pashmak and Parmida's Problem

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;
typedef pair<int, int> pii;

const int N = 1e6;

vector<pii> newArr;
int arr[N + 1], fi[N + 1], fj[N + 1];

lli ans = 0;
int mergeSort(vector<pii> &v, int l, int r){
    if(l == r){
        return v[l].second;
    }
    int m = (l + r) / 2;
    int cntLeft = mergeSort(v, l, m);
    int cntRight = mergeSort(v, m + 1, r);
    int cnt = cntRight;
    pii tmp[r - l + 1];
    int i = l;
    int j = m + 1;
    int k = 0;
    while(i <= m && j <= r){
        if(v[i].first > v[j].first){
            tmp[k++] = v[i];
            if(v[i].second == 0){
                ans += cnt;
            }
            ++i;
        } else {
            tmp[k++] = v[j];
            if(v[j].second == 1){
                --cnt;
            }
            ++j;
        }
    }
    while(i <= m){
        tmp[k++] = v[i++];
    }
    while(j <= r){
        tmp[k++] = v[j++];
    }
    for(int i = l; i <= r; ++i){
        v[i] = tmp[i - l];
    }
    return cntLeft + cntRight;
}

int main(){

    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        scanf("%d", &arr[i]);
    }
    map<int, int> mp;
    for(int i = 1; i <= n; ++i){
        ++mp[arr[i]];
        fi[i] = mp[arr[i]];
    }
    mp.clear();
    for(int i = n; i >= 1; --i){
        ++mp[arr[i]];
        fj[i] = mp[arr[i]];
    }
    for(int i = 1; i <= n; ++i){
        newArr.emplace_back(fj[i], 1);
        newArr.emplace_back(fi[i], 0);
    }
    mergeSort(newArr, 0, (int)newArr.size() - 1);
    cout << ans;

    return 0;
}

// Fenwick Solution
#include <bits/stdc++.h>
using namespace std;

typedef long long lli;

const int N = 1e6;
const int logN = log2(N);

map<int, int> mp;
int arr[N + 1], fi[N + 1], fj[N + 1], fw[N + 1], n;

void fwUpdate(int i, int x){
    for(; i <= n; i += (i & -i)){
        fw[i] += x;
    }
}

int fwQuery(int i){
    int sum = 0;
    for(; i >= 1; i -= (i & -i)){
        sum += fw[i];
    }
    return sum;
}

int main(){

    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        scanf("%d", &arr[i]);
        ++mp[arr[i]];
        fi[i] = mp[arr[i]];
    }
    mp.clear();
    lli ans = 0;
    for(int i = n; i >= 1; --i){
        ++mp[arr[i]];
        fj[i] = mp[arr[i]];
        ans += fwQuery(fi[i] - 1);
        fwUpdate(fj[i], 1);
    }
    cout << ans;

    return 0;
}