in c++

cpp
long findTotalEfficiency(vector<int> arr, vector<vector<int>> pairs) {
    int n = arr.size();

    // 1) Count how many times each index appears in the concatenated efficient array
    vector<long long> diff(n + 1, 0);

    for (auto &p : pairs) {
        int l = p[0];
        int r = p[1];
        diff[l]++;
        if (r + 1 < n) diff[r + 1]--;
    }

    vector<long long> cover(n, 0);
    long long cur = 0;
    for (int i = 0; i < n; i++) {
        cur += diff[i];
        cover[i] = cur;
    }

    // 2) Coordinate compress arr values
    vector<int> vals = arr;
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    int k = vals.size();
    vector<long long> freq(k, 0);

    // freq[x] = how many times value x appears in efficient array
    for (int i = 0; i < n; i++) {
        if (cover[i] > 0) {
            int idx = lower_bound(vals.begin(), vals.end(), arr[i]) - vals.begin();
            freq[idx] += cover[i];
        }
    }

    // 3) Prefix sums: count of efficient elements with value <= vals[i]
    vector<long long> pref(k, 0);
    pref[0] = freq[0];
    for (int i = 1; i < k; i++) {
        pref[i] = pref[i - 1] + freq[i];
    }

    // 4) For indices not included in efficient array, count smaller values
    long long ans = 0;

    for (int i = 0; i < n; i++) {
        if (cover[i] == 0) {
            int idx = lower_bound(vals.begin(), vals.end(), arr[i]) - vals.begin();

            if (idx > 0) {
                ans += pref[idx - 1];
            }
        }
    }

    return ans;
}

This handles duplicate intervals correctly because cover[i] stores how many times index i contributes to efficient.

Time complexity: O((n + m) log n)
Space complexity: O(n)