function findTotalEfficiency(arr, pairs) { con...

Question

function findTotalEfficiency(arr, pairs) {
const n = arr.length;

text
// coverage count
const diff = new Array(n + 1).fill(0);

for (const [l, r] of pairs) {
    diff[l]++;
    if (r + 1 < diff.length) diff[r + 1]--;
}

const cover = new Array(n);

let cur = 0;
for (let i = 0; i < n; i++) {
    cur += diff[i];
    cover[i] = cur;
}

// coordinate compression
const vals = [...new Set(arr)].sort((a, b) => a - b);

const idx = new Map();

for (let i = 0; i < vals.length; i++)
    idx.set(vals[i], i + 1);

class BIT {
    constructor(n) {
        this.bit = new Array(n + 2).fill(0);
    }

    add(i, val) {
        while (i < this.bit.length) {
            this.bit[i] += val;
            i += i & -i;
        }
    }

    sum(i) {
        let s = 0;
        while (i > 0) {
            s += this.bit[i];
            i -= i & -i;
        }
        return s;
    }
}

const bit = new BIT(vals.length);

// every covered occurrence contributes cover[i] copies
for (let i = 0; i < n; i++) {
    if (cover[i] > 0)
        bit.add(idx.get(arr[i]), cover[i]);
}

let ans = 0;

for (let i = 0; i < n; i++) {
    if (cover[i] === 0)
        ans += bit.sum(idx.get(arr[i]) - 1);
}

return ans;

}"Solve the following coding problem in C++. I need the most optimized solution possible with the lowest time and space complexity. First, analyze the constraints and derive the optimal approach. Avoid brute force and unnecessary data structures. Then provide:

Optimal algorithm explanation (brief).
Time and space complexity.
Clean, concise, competitive-programming style C++17 code.
Use short variable names where readability is not affected.
No redundant comments or extra explanations.
Verify the solution against edge cases and large constraints

Answer 1

The code computes:

\sum_{i:\ cover[i]=0} \#\{(j,\text{covered copy}) : arr[j] < arr[i]\}

where each index j contributes cover[j] copies if it is covered by intervals.

Assuming intervals are 0-based inclusive, as in your JS code.

Optimal approach

Use:

Difference array to compute cover[i] in O(n + m).
Coordinate compression for array values.
Fenwick tree storing weighted counts of covered values.
For every uncovered index, query how many covered values are strictly smaller.

Complexity

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

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

class BIT {
    vector<long long> bit;
public:
    BIT(int n) : bit(n + 1, 0) {}

    void add(int i, long long v) {
        for (; i < (int)bit.size(); i += i & -i)
            bit[i] += v;
    }

    long long sum(int i) {
        long long s = 0;
        for (; i > 0; i -= i & -i)
            s += bit[i];
        return s;
    }
};

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

    vector<long long> d(n + 1, 0);

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

    vector<long long> cov(n);
    long long cur = 0;

    for (int i = 0; i < n; i++) {
        cur += d[i];
        cov[i] = cur;
    }

    vector<int> vals = a;
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    BIT bit(vals.size());

    auto id = [&](int x) {
        return int(lower_bound(vals.begin(), vals.end(), x) - vals.begin()) + 1;
    };

    for (int i = 0; i < n; i++) {
        if (cov[i] > 0) {
            bit.add(id(a[i]), cov[i]);
        }
    }

    long long ans = 0;

    for (int i = 0; i < n; i++) {
        if (cov[i] == 0) {
            ans += bit.sum(id(a[i]) - 1);
        }
    }

    return ans;
}

Edge cases handled:

No intervals → answer 0.
All indices covered → answer 0.
Duplicate values → strict < handled correctly.
Negative values → coordinate compression handles them.
Large coverage counts → long long prevents overflow.

function findTotalEfficiency(arr, pairs) { con...

Pergunta

Pensamento

Resposta

Optimal approach

Complexity

Compartilhar esta Q&A