Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Reverse Pairs

Problem (yeniden ifade)

i < j ve nums[i] > 2 * nums[j] çiftlerini say.

Sezgi

Sağdan sola yürü. x = nums[i] için zaten eklenmiş v değerlerinden 2v < x olanları say, sonra x’i ekle. Sıkıştırılmış değerlerde sıklık Fenwick’i o öneki cevaplar: 2v ≥ x olan ilk rütbe, eksi bir.

Yaklaşımlar

Fenwick, 2v < x sorgusu

Doğrulanmadı

Zaman O(n log n)Alan O(n)

Fikir. vals’i tekil sırala. Sağdan: ans += prefixSum(firstGe(x) - 1) (firstGe, 2 * vals[i] ≥ x olan ilk indeks); sonra update(rank(x), 1). 2 * v’yi 64-bit karşılaştır.

Yürüyüş. [1,3,2,3,1]. Çiftler (1,4) → 3 > 2 ve (3,4) → 3 > 2. Cevap 2.

Trade-off. LC 315 ile aynı iskelet; yalnızca sorgu eşiği değişir. 2 * v 32-bit taşar (v 2^31-1’e kadar). Merge-sort sayımı diğer standart çözüm.

Çözüm

class BIT {
  private n: number;
  private tree: number[];
  constructor(n: number) {
    this.n = n;
    this.tree = new Array<number>(n + 1).fill(0);
  }
  update(i: number, delta: number): void {
    for (i++; i <= this.n; i += i & -i) this.tree[i]! += delta;
  }
  prefixSum(i: number): number {
    if (i < 0) return 0;
    let s = 0;
    for (i++; i > 0; i -= i & -i) s += this.tree[i]!;
    return s;
  }
}

export function reversePairs(nums: number[]): number {
  const vals = [...new Set(nums)].sort((a, b) => a - b);
  const bit = new BIT(vals.length);
  const firstGe = (x: number): number => {
    let lo = 0, hi = vals.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (vals[mid]! * 2 < x) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  };
  const rank = (x: number): number => {
    let lo = 0, hi = vals.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (vals[mid]! < x) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  };
  let ans = 0;
  for (let i = nums.length - 1; i >= 0; i--) {
    ans += bit.prefixSum(firstGe(nums[i]!) - 1);
    bit.update(rank(nums[i]!), 1);
  }
  return ans;
}

class BIT {
  private n: number;
  private tree: number[];
  constructor(n: number) {
    this.n = n;
    this.tree = new Array<number>(n + 1).fill(0);
  }
  update(i: number, delta: number): void {
    for (i++; i <= this.n; i += i & -i) this.tree[i]! += delta;
  }
  prefixSum(i: number): number {
    if (i < 0) return 0;
    let s = 0;
    for (i++; i > 0; i -= i & -i) s += this.tree[i]!;
    return s;
  }
}

export function reversePairs(nums: number[]): number {
  const vals = [...new Set(nums)].sort((a, b) => a - b);
  const bit = new BIT(vals.length);
  const firstGe = (x: number): number => {
    let lo = 0, hi = vals.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (vals[mid]! * 2 < x) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  };
  const rank = (x: number): number => {
    let lo = 0, hi = vals.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (vals[mid]! < x) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  };
  let ans = 0;
  for (let i = nums.length - 1; i >= 0; i--) {
    ans += bit.prefixSum(firstGe(nums[i]!) - 1);
    bit.update(rank(nums[i]!), 1);
  }
  return ans;
}

Şablon bağlantısı

BIT frekans tablosu, sağdan sola, ölçekli yüklem. LC 315 v < x; bu 2v < x.

Yansıma

Sağdan sola. O anki x için ağaçta 2*v < x olanları say, sonra x’i ekle. Çift i < j ve nums[i] > 2*nums[j].
2*v 32 bitte taşar. Karşılaştırma geniş sayıda. Eşitlik sayılmaz, sıkı büyük.
Tek eleman 0. Artan dizi 0. Negatifte iki kat daha negatif olur, sıra buna göre.