Coordinate Compression

// Given values that can be up to 10^9, compress to ranks 1..n
function compress(values) {
    // Step 1: collect all unique values
    const unique = [...new Set(values)].sort((a,b) => a-b);
    // Step 2: build rank map
    const rank = new Map(unique.map((v,i) => [v, i+1])); // 1-indexed
    // Step 3: replace values with ranks
    return { ranks: values.map(v => rank.get(v)), n: unique.length, rank, unique };
}

// Lower bound: rank of x = first rank with unique[rank-1] >= x
// Used for: "count elements less than x" = query(lowerBound(x) - 1)

// Example: values = [100, 50, 200, 50, 100]
// unique = [50, 100, 200] → ranks: [2, 1, 3, 1, 2]
// Fenwick tree of size 3 instead of 200!

// Combined with Fenwick tree for counting/inversions:
function countInversions(nums) {
    const unique = [...new Set(nums)].sort((a,b)=>a-b);
    const rank = new Map(unique.map((v,i)=>[v,i+1]));
    const n = unique.length;
    const bit = new Array(n+1).fill(0);
    const update = i => { for(;i<=n;i+=i&(-i)) bit[i]++; };
    const query = i => { let s=0; for(;i>0;i-=i&(-i)) s+=bit[i]; return s; };
    let inversions = 0;
    for(const x of nums) {
        const r = rank.get(x);
        inversions += query(n) - query(r); // count elements already inserted that are > x
        update(r);
    }
    return inversions;
}