mega inversions count

template<class T, class iter>
class inversion_counter {
    vector<iter> sorted;
    vector<iter> additional;
    vector<uint64_t> ans;
    vector<vector<uint64_t>::iterator> sorted_ans;
    vector<vector<uint64_t>::iterator> additional_ans;
    void count(const iter& a, const iter& b,
               typename vector<iter>::iterator sl, typename vector<iter>::iterator sr,
               vector<vector<uint64_t>::iterator>::iterator al, vector<vector<uint64_t>::iterator>::iterator ar) {
        if (distance(sl, sr) <= 1) {
            if (sl != sr) {
                *sl = a;
                *al = ans.begin() + distance(sorted.begin(), sl);
            }
            return;
        }
        iter mid = next(a, distance(a, b) / 2);
        typename vector<iter>::iterator sm = next(sl, distance(a, b) / 2);
        vector<vector<uint64_t>::iterator>::iterator am = next(al, distance(a, b) / 2);
        count(a, mid, sl, sm, al, am);
        count(mid, b, sm, sr, am, ar);
        typename vector<iter>::iterator it = sl, jt = sm;
        typename vector<iter>::iterator vi = additional.begin();
        vector<vector<uint64_t>::iterator>::iterator ai = al, aj = am;
        vector<vector<uint64_t>::iterator>::iterator avi = additional_ans.begin();
        while (it != sm || jt != sr) {
            if ((jt != sr) && (it == sm || **jt < **it)) {
                *(vi++) = *jt;
                **aj += distance(it, sm);
                *(avi++) = *aj;
                aj++;
                jt++;
            } else {
                *(vi++) = *it;
                *(avi++) = *ai;
                ai++;
                it++;
            }
        }
        copy(additional.begin(), vi, sl);
        copy(additional_ans.begin(), avi, al);
    }
  public:
    inversion_counter(const iter& a, const iter& b) {
        sorted.resize(distance(a, b));
        additional.resize(distance(a, b));
        ans.resize(distance(a, b), 0);
        sorted_ans.resize(distance(a, b));
        additional_ans.resize(distance(a, b));
        count(a, b, all(sorted), all(sorted_ans));
    }
    const vector<uint64_t>& operator()() const {
        return ans;
    }
};

template<class T>
uint64_t mega_inversion_count(const vector<T>& vec) {
    vector<uint64_t> frw_inv = inversion_counter<T, typename vector<T>::const_iterator>(all(vec))();
    vector<uint64_t> bkw_inv = inversion_counter<T, typename vector<T>::const_reverse_iterator>(rall(vec))();
    forn(i, vec.size()) {
        bkw_inv[i] = i - bkw_inv[i];
    }
    reverse(all(bkw_inv));
    uint64_t ans = 0;
    forn(i, vec.size()) {
        ans += frw_inv[i] * bkw_inv[i];
    }
    return ans;
}