实战：计算右侧小于当前元素的个数 ​

function countSmaller(nums: number[]): number[] {
  const result: number[] = [];
  
  for (let i = 0; i < nums.length; i++) {
    let count = 0;
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] < nums[i]) count++;
    }
    result.push(count);
  }
  
  return result;
}

function countSmaller(nums: number[]): number[] {
  const n = nums.length;
  const result = new Array(n).fill(0);
  
  // 存储 (值, 原始索引) 对
  const pairs: [number, number][] = nums.map((val, idx) => [val, idx]);
  
  function mergeSort(left: number, right: number): void {
    if (left >= right) return;
    
    const mid = Math.floor((left + right) / 2);
    mergeSort(left, mid);
    mergeSort(mid + 1, right);
    merge(left, mid, right);
  }
  
  function merge(left: number, mid: number, right: number): void {
    const temp: [number, number][] = [];
    let i = left, j = mid + 1;
    
    while (i <= mid && j <= right) {
      if (pairs[i][0] <= pairs[j][0]) {
        // 右边有 j - (mid + 1) 个元素已经被选走
        // 它们都小于 pairs[i][0]
        result[pairs[i][1]] += j - (mid + 1);
        temp.push(pairs[i]);
        i++;
      } else {
        temp.push(pairs[j]);
        j++;
      }
    }
    
    // 左边剩余元素
    while (i <= mid) {
      result[pairs[i][1]] += j - (mid + 1);
      temp.push(pairs[i]);
      i++;
    }
    
    // 右边剩余元素
    while (j <= right) {
      temp.push(pairs[j]);
      j++;
    }
    
    // 复制回原数组
    for (let k = 0; k < temp.length; k++) {
      pairs[left + k] = temp[k];
    }
  }
  
  mergeSort(0, n - 1);
  return result;
}

function countSmaller(nums: number[]): number[] {
  // 离散化
  const sorted = [...new Set(nums)].sort((a, b) => a - b);
  const rank = new Map<number, number>();
  sorted.forEach((v, i) => rank.set(v, i + 1));
  
  const n = nums.length;
  const result = new Array(n);
  const tree = new Array(sorted.length + 1).fill(0);
  
  // 从右向左遍历
  for (let i = n - 1; i >= 0; i--) {
    const r = rank.get(nums[i])!;
    result[i] = query(tree, r - 1);  // 查询比当前小的数量
    update(tree, r);                  // 更新当前元素
  }
  
  return result;
}

function update(tree: number[], i: number): void {
  while (i < tree.length) {
    tree[i]++;
    i += i & (-i);
  }
}

function query(tree: number[], i: number): number {
  let sum = 0;
  while (i > 0) {
    sum += tree[i];
    i -= i & (-i);
  }
  return sum;
}

// ❌ 错误：左边剩余元素没有统计
while (i <= mid && j <= right) {
  // ...
}
// 忘记处理 i <= mid 的情况

// ✅ 正确：左边剩余元素也要统计
while (i <= mid) {
  result[pairs[i][1]] += j - (mid + 1);  // 右边全部选完了
  temp.push(pairs[i++]);
}

// ❌ 错误：直接修改result数组
result[i] += count;  // i 是当前遍历位置，不是原始索引

// ✅ 正确：使用pairs中存储的原始索引
result[pairs[i][1]] += count;  // pairs[i][1] 是原始索引

// ❌ 错误：只存值，丢失索引
temp.push(pairs[i][0]);  // 只存值

// ✅ 正确：存储完整的 (值, 索引) 对
temp.push(pairs[i]);  // 存整个对象