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

Create Sorted Array through Instructions

Problem (yeniden ifade)

Boş listeyle başla. Her talimat x için x’i sıralı listeye ekle, min(< x olan mevcut değer sayısı, > x olan mevcut değer sayısı) öde. Toplam maliyeti 10^9+7 modunda döndür.

Sezgi

Listenin kendisi gerekmez — yalnızca eklenen sayılardan kaçının x’ten kesin küçük / kesin büyük olduğu. Sıkıştırılmış rütbede sıklık Fenwick’i: less = prefix(rank-1), greater = total - prefix(rank) (≤ x olanlar toplamdan düşülür). Sonra ekle.

Yaklaşımlar

Fenwick, min(less, greater)

Doğrulanmadı

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

Fikir. Tekil talimat değerlerini sıkıştır. Her x için: min(less, greater)’ı cevaba ekle, update(rank[x], 1), total++. x eşitleri prefix(rank) içinde, ne less ne greater.

Yürüyüş. [1,5,6,2]. 1 ekle (0). 5 ekle (0). 6 ekle (0). 2 ekle: less=1, greater=2 → maliyet 1. Toplam 1.

Trade-off. Kalıp sayfası bu id için lazy range-add listeler; her ekleme tek değer olduğu için nokta-güncelleme sıklık BIT yeter. Her eklemede mod.

Çö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 createSortedArray(instructions: number[]): number {
  const MOD = 1_000_000_007;
  const vals = [...new Set(instructions)].sort((a, b) => a - b);
  const rank = new Map<number, number>();
  vals.forEach((v, i) => rank.set(v, i));
  const bit = new BIT(vals.length);
  let ans = 0, total = 0;
  for (const x of instructions) {
    const r = rank.get(x)!;
    const less = bit.prefixSum(r - 1);
    const greater = total - bit.prefixSum(r);
    ans = (ans + Math.min(less, greater)) % MOD;
    bit.update(r, 1);
    total++;
  }
  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 createSortedArray(instructions: number[]): number {
  const MOD = 1_000_000_007;
  const vals = [...new Set(instructions)].sort((a, b) => a - b);
  const rank = new Map<number, number>();
  vals.forEach((v, i) => rank.set(v, i));
  const bit = new BIT(vals.length);
  let ans = 0, total = 0;
  for (const x of instructions) {
    const r = rank.get(x)!;
    const less = bit.prefixSum(r - 1);
    const greater = total - bit.prefixSum(r);
    ans = (ans + Math.min(less, greater)) % MOD;
    bit.update(r, 1);
    total++;
  }
  return ans;
}

Şablon bağlantısı

BIT dinamik sıralı multiset: önek sayımları less/equal verir, total - equal greater. LC 315 yalnızca less, sağdan sola.

Yansıma

Sıkıştırılmış sırada, eklemeden önce küçük ve büyük say. Maliyet min(küçük, büyük). Sonra 1 ekle.
Eşit değer ne küçük ne büyük. Toplam 10**9+7 modunda.
İlk talimat 0. Aynı sayı tekrar gelirse maliyetsiz. BIT 1-index.