Temu Duga Pengekodan: Bagaimanakah anda menggunakan Li Chao tree untuk pertanyaan minimum garis dinamik?

Masalah dan Konteks

Perkhidmatan dalam talian menerima garis y = m x + b dalam susunan sisipan sewenang-wenangnya dan mesti mengembalikan nilai minimum pada titik pertanyaan integer x. Titik pertanyaan juga adalah sewenang-wenangnya. Lanjutan masalah mungkin mengehadkan garis kepada selang [l, r] atau meminta nilai maksimum sebagai ganti.

Masalah ini menguji pengoptimuman pengaturcaraan dinamik, invarian pecah dan perintah (divide-and-conquer), dan pelaksanaan segment tree. Jawapan yang mantap menyatakan terlebih dahulu sama ada domain pertanyaan adalah diskret dan terikat, kemudian menerangkan sebab setiap nod boleh mengekalkan satu garis yang menang di suatu tempat sementara mana-mana calon yang tinggal dihantar ke tepat satu nod anak.

Perkara yang Dinilai oleh Penemu Duga

Menerbitkan kekangan (bottleneck) daripada mengimbas setiap garis dalam O(number_of_lines) bagi setiap pertanyaan.
Memahami perbandingan titik tengah, pertukaran (swap), dan invarian rekursi.
Mengendalikan kecerunan sewenang-wenangnya, garis pendua, koordinat negatif, dan limpahan (overflow).
Membezakan domain integer diskret, domain selanjar, dan garis yang dihadkan oleh tembereng.
Memberikan batas sisipan/pertanyaan O(log C) dan sisipan tembereng O(log^2 C).
Menerangkan bila kecerunan monoton dan pertanyaan monoton menjadikan convex hull trick standard lebih mudah.

Penjelasan yang Perlu Ditanya Terlebih Dahulu

Adakah titik pertanyaan merupakan integer atau nombor nyata? Adakah domain ditetapkan [L, R] atau diperluaskan secara dinamik? Ini menentukan kedalaman dan pemampatan koordinat.
Adakah operasinya nilai minimum atau maksimum? Adakah set kosong dibenarkan, dan apakah sentinel yang tidak akan bertembung dengan jawapan sebenar?
Apakah magnitud maksimum bagi kecerunan, pintasan, dan jawapan? Adakah jenis integer yang lebih luas atau pendaraban yang disemak diperlukan?
Adakah garis hanya terpakai pada [l, r]? Sisipan selang mengedarkan garis kepada beberapa nod pokok.
Adakah kecerunan sisipan atau titik pertanyaan monoton? Jika ya, convex hull trick berasaskan deque mungkin menggunakan pemalar yang lebih kecil.

Rangka Kerja Jawapan 30 Saat

Saya membina domain segment tree [L, R] dan menyimpan satu garis calon pada setiap nod. Semasa menyisipkan garis baharu, saya membandingkannya dengan garis nod pada titik hujung dan titik tengah. Jika garis baharu menang pada titik tengah, saya menukarnya ke dalam nod. Garis yang digantikan masih boleh menang hanya pada separuh kiri atau kanan, jadi saya melakukan rekursi ke dalam satu nod anak. Pertanyaan titik menilai setiap garis pada laluan dari punca ke daun (root-to-leaf) dan mengambil nilai minimum. Dengan panjang domain C, sisipan dan pertanyaan ialah O(log C); mengehadkan garis kepada selang memerlukan kos O(log^2 C). Pertanyaan maksimum menyongsangkan pembanding.

Penelitian Terperinci Langkah demi Langkah

1. Brute Force dan Kekangan

Simpan senarai garis dan nilai setiap m x + b bagi setiap pertanyaan. Ini memerlukan kos O(number_of_lines) bagi setiap pertanyaan. Dalam peralihan pengaturcaraan dinamik, sisipan dan pertanyaan diselang-selikan, jadi kecerunan mahupun titik pertanyaan tidak boleh diisih tanpa mengubah masalah. Struktur data mesti mengedarkan perbandingan ke atas domain nilai.

2. Invarian Nod

Nod mewakili selang tertutup [lo, hi] dan menyimpan garis cur. Antara garis yang belum ditolak ke nod anak, cur tidak lebih buruk pada sekurang-kurangnya satu kedudukan calon dalam selang ini. Mana-mana garis lain yang masih boleh menjadi optimum hanya boleh berbuat demikian pada nod anak kiri atau kanan. Pada daun, nod hanya memerlukan garis yang terbaik pada satu titik.

3. Pertukaran Titik Tengah dan Arah Rekursi

Biar nw menjadi garis baharu, cur garis nod, dan mid titik tengah. Jika nilai garis baharu pada mid adalah lebih kecil, tukarkannya supaya nod mengekalkan pemenang titik tengah. Selepas pertukaran, bandingkan garis mana yang menang pada lo. Jika garis yang digantikan menang pada titik hujung kiri, ia mungkin muncul semula hanya pada separuh kiri; jika tidak, bandingkan titik hujung kanan dan lakukan rekursi ke kanan. Perbezaan dua garis adalah linear, jadi susunannya berubah paling banyak sekali.

text

add(node, lo, hi, nw):
  mid = (lo + hi) // 2
  left = nw(lo) < cur(lo)
  middle = nw(mid) < cur(mid)
  if middle: swap(nw, cur)
  if lo == hi: return
  if left != middle: add(leftChild, lo, mid, nw)
  else: add(rightChild, mid + 1, hi, nw)

Gunakan formula titik tengah yang selamat. Jika m * x + b boleh melebihi julat 64-bit, gunakan jenis yang lebih luas, aritmetik yang disemak, atau dasar ketepuan eksplisit.

4. Menyoal Laluan Root-to-Leaf

Untuk titik x, lakukan rekursi ke arah daun yang mengandungi x, nilai garis yang disimpan pada x pada setiap nod yang dilawati, dan kembalikan nilai minimum. Subpokok lain tidak mengandungi titik tersebut. Pokok tersirat (implicit tree) memperuntukkan nod hanya pada laluan yang disentuh oleh sisipan; nod kosong mengembalikan sentinel infiniti positif.

5. Sisipkan Garis yang Dihadkan kepada Selang

Jika garis sah hanya pada [ql, qr], huraikan selang tersebut dengan segment tree standard. Sisipkan garis sekali ke dalam setiap nod yang diliputi sepenuhnya dan lakukan rekursi untuk liputan separa. Penghuraian ini menyentuh O(log C) nod dan setiap sisipan Li Chao memerlukan kos O(log C), memberikan O(log^2 C); pertanyaan titik kekal O(log C).

6. Koordinat Diskret dan Pertanyaan Selanjar

Jika pertanyaan datang daripada set terhingga yang diketahui, isih dan nyahduplikasi nilai x serta gunakan indeksnya sebagai daun. Ini mengelakkan pembinaan domain kosong yang besar. Untuk pertanyaan bernilai nyata, nyatakan kejituan dan syarat berhenti secara eksplisit. Pembuktian domain integer tidak terpakai secara automatik kepada domain selanjar tidak terikat; batasi selang dan takrifkan toleransi perbandingan titik terapung.

7. Pertukaran (Trade-offs) dan Ujian

Apabila kedua-dua kecerunan dan titik pertanyaan adalah monoton, convex hull trick berasaskan deque mempunyai pemalar yang lebih kecil. Li Chao adalah lebih teguh untuk susunan sewenang-wenangnya, dengan kos nod dan rekursi yang lebih banyak. Uji set kosong, domain satu titik, kecerunan pendua, garis yang serupa, koordinat negatif, persilangan pada titik tengah, garis yang meliputi satu titik hujung, hasil darab yang besar, dan pertanyaan maksimum; bandingkan setiap hasil dengan penilaian brute-force.

Jawapan Model Berkualiti Tinggi

Saya akan mengesahkan terlebih dahulu sama ada domain pertanyaan ialah selang integer terikat atau memerlukan pemampatan koordinat. Untuk [L, R], saya membina Li Chao tree yang nodnya menyimpan garis calon. Sisipan membandingkan titik hujung dan titik tengah; pemenang titik tengah kekal di nod, dan garis yang satu lagi melakukan rekursi ke dalam bahagian separuh di mana kedua-dua garis boleh bertukar susunan. Perbezaan kedua-duanya adalah linear, jadi garis yang digantikan tidak boleh menjadi lebih baik dalam dua arah yang terpisah. Pertanyaan titik mengambil nilai minimum di sepanjang satu laluan root-to-leaf, memberikan O(log C) untuk sisipan dan pertanyaan. Jika kecerunan dan pertanyaan adalah monoton, saya akan menggunakan convex hull trick; garis yang dihadkan kepada selang memerlukan penghuraian tembereng dan sisipan O(log^2 C).

Kesilapan Lazim

Membandingkan titik tengah sahaja dan berhenti → garis lain mungkin menang pada titik hujung → gunakan perbandingan titik hujung dan titik tengah untuk memilih satu nod anak.
Menganggap kecerunan mestilah monoton → sisipan sewenang-wenangnya menghasilkan jawapan yang salah → gunakan invarian selang Li Chao atau nyatakan prasyarat convex-hull.
Mengira m * x + b dalam aritmetik 64-bit yang tidak disemak → limpahan mengubah perbandingan → gunakan aritmetik yang lebih luas atau disemak.
Membenarkan domain dinamik tidak terikat → rekursi tidak mempunyai penamatan → batasi domain integer, mampatkan koordinat, atau takrifkan kejituan titik terapung.
Menyalin garis selang ke setiap daun → kekompleksan merosot → huraikan selang dan sisipkan pada nod yang diliputi sepenuhnya.
Mengembalikan sifar untuk nod kosong → nilai minimum diturunkan secara salah → gunakan sentinel infiniti positif di luar julat jawapan.

Soalan Susulan dan Maklum Balas

Apakah yang berubah untuk pertanyaan maksimum?

Songsangkan setiap perbandingan, atau nafikan kedua-dua m dan b, selesaikan pertanyaan minimum, dan nafikan hasilnya. Semantik set kosong dan limpahan mesti disongsangkan secara konsisten dan bukannya menukar nilai pulangan akhir sahaja.

Bolehkah pokok berasaskan tatasusunan mengendalikan domain 10 kuasa 18?

Bukan dengan memperuntukkan setiap nod terlebih dahulu. Gunakan pokok tersirat yang mencipta nod hanya di sepanjang laluan sisipan; kedalamannya kira-kira bilangan bit domain. Jika koordinat pertanyaan adalah terhingga, pemampatan koordinat biasanya menjimatkan lebih banyak memori.

Dua garis seri pada titik tengah. Bagaimanakah anda mengelakkan cabang yang salah?

Pilih peraturan pemutus seri yang deterministik, seperti mengekalkan garis lama atau mengutamakan susunan kecerunan. Gunakan ketaksamaan ketat secara konsisten pada titik hujung dan titik tengah supaya garis yang serupa tidak melakukan rekursi selama-lamanya.

Mengapakah satu sisi rekursif sahaja mencukupi?

Perbezaan dua garis adalah linear dan mempunyai paling banyak satu sifar. Selepas pemenang titik tengah dikekalkan, garis yang digantikan hanya boleh pulih ke arah titik hujung yang susunannya berbeza, sekali gus memilih nod anak kiri atau kanan secara unik.

Bilakah convex hull trick lebih baik?

Jika garis tiba dalam susunan kecerunan monoton dan pertanyaan adalah monoton, deque hull boleh menyediakan pertanyaan O(1) yang dilunaskan atau pertanyaan carian binari O(log n) dengan memori yang lebih sedikit. Susunan sewenang-wenangnya, atau garis yang dihadkan oleh tembereng, lebih memihak kepada keumuman Li Chao.