บทที่ 30 หัวข้อเสริม
จบบทนี้ น้องจะเรียงงานที่มีเงื่อนไขก่อนหลังด้วย topological sort ตรวจได้ว่าเงื่อนไขวนกันหรือไม่ และหาเส้นทางที่ยาวที่สุดบนกราฟที่ไม่มีวงด้วย DP จะมีโครงสร้างข้อมูลสองตัวที่รับทั้งการปรับค่าและการถามช่วงสลับกันไปได้ใน O(log N) คือ Fenwick tree สำหรับผลรวม และ segment tree สำหรับค่าต่ำสุด ค่าสูงสุด และการรวมแบบอื่น ปิดท้ายด้วยการค้นหาคำในข้อความใน O(n + m) ด้วย prefix function เครื่องมือเหล่านี้ใช้กับโจทย์ที่ข้อมูลเปลี่ยนไปเรื่อยๆ ระหว่างที่ต้องตอบคำถาม และโจทย์ลำดับงาน ซึ่งวิธีจากบทก่อนๆ ช้าเป็น O(NQ) หรือ O(N2)
บทนี้ไม่ใช่เนื้อหาบังคับของค่าย 2
หัวข้อในบทนี้ไม่ได้ระบุไว้ชัดในหลักสูตรค่าย สอวน. บทนี้มีไว้สำหรับน้องที่จะแข่ง TOI ต่อ ถ้ากำลังเตรียมค่าย 2 ให้ทำบทที่ 18 ถึง 29 ให้คล่องก่อน แล้วค่อยกลับมาอ่านบทนี้ IOI Syllabus ฉบับที่ใช้กับ IOI 2023 นับ topological sort Fenwick tree และ segment tree ว่าอยู่ในขอบเขต แต่จัด KMP และอัลกอริทึมสตริงแบบอื่นไว้ในกลุ่มที่ไม่ออกข้อสอบ หน้า 30.4 จึงเสริมยิ่งกว่าหน้าอื่น
ในบทนี้
| หน้า | ได้อะไร |
|---|---|
| 30.1 topological sort และ DP บน DAG | Kahn ด้วย in-degree กับ queue ตรวจวง DFS แบบสามสถานะ เส้นทางที่ได้คะแนนมากสุดบน DAG และกับดักทำ DP ตามเลขจุด |
| 30.2 Fenwick tree | ก้อนตามเลขฐานสอง i & -i ปรับค่าและหาผลรวม prefix ใน O(log N) บวกทั้งช่วงแล้วถามทีละช่อง และกับดักช่อง 0 กับการแทนค่า |
| 30.3 segment tree | ต้นไม้ของช่วง ถามค่าต่ำสุดและปรับค่าช่องเดียวใน O(log N) ทำไมต้องจอง 4N เปลี่ยนเป็นผลรวมหรือค่าสูงสุด และ lazy propagation ที่มีอยู่ |
| 30.4 ค้นหาข้อความด้วย prefix function | border และ prefix function ใน O(n) ค้นหาคำด้วยตัวคั่น และข้อมูลที่ทำให้วิธีไล่กับ string::find ช้า |
ผ่านบทนี้เมื่อ
หลังจากบทนี้
บทนี้เป็นบทสุดท้ายของเว็บ ถึงตรงนี้น้องมีเครื่องมือครบสำหรับโจทย์ค่าย 2 และโจทย์ TOI ส่วนใหญ่แล้ว สิ่งที่ช่วยได้มากที่สุดต่อจากนี้คือทำโจทย์เก่าให้มาก จับเวลาเหมือนแข่งจริง อ่านขอบเขตก่อนเลือกวิธีตามหน้า 18.2 และทุกครั้งที่ผิด ให้ย้อนดูว่าเป็นกับดักแบบไหนในส่วนลองทำให้พังของบทต่างๆ