programming.in.th · ข้อ 2013

ฐานปิรามิด: ตารางล้านคูณล้านที่ไม่ต้องแตะสักช่อง

กลับไปถามที่มุมล่างซ้ายของฐาน แล้วก้อนแต่ละก้อนจะกลายเป็นสี่เหลี่ยมบวกค่าที่ไล่ทีละคอลัมน์ได้ ส่วนชุดงบศูนย์ใช้ช่วงคอลัมน์ที่ยืดหดเองแทนการเดาขนาด

★★★★★ binary searchsweep linesegment tree อ่าน 17 นาที เผยแพร่ 7 กันยายน 2026 อัปเดต 19 ตุลาคม 2026

โจทย์ · หาที่วางฐานปิรามิดให้ใหญ่ที่สุดในงบที่มี

พื้นที่สำรวจเป็นตารางขนาด M × N ช่อง ฐานปิรามิดต้องเป็นจัตุรัสที่ด้านขนานกับเส้นตาราง บนพื้นที่มีสิ่งกีดขวาง P ก้อน แต่ละก้อนเป็นสี่เหลี่ยมในตาราง (ทับซ้อนกันได้)

การทำลายก้อนที่ i เสียค่าใช้จ่าย C และต้องทำลายทั้งก้อน จะทุบแค่ส่วนที่ขวางไม่ได้ เรามีงบ B งานคือหาด้านที่ยาวที่สุดของฐานที่วางได้ โดยค่าทำลายก้อนที่ทับฐานรวมแล้วไม่เกินงบ ถ้าวางไม่ได้เลยให้ตอบ 0

อินพุต / ขอบเขต / เอาต์พุต

EXAMPLE
InputOutput
6 9
42
5
4 1 6 3 12
3 6 5 6 9
1 3 3 8 24
3 8 6 9 21
5 1 6 2 20
 4
13 5
0
8
8 4 10 4 1
4 3 4 4 1
10 2 12 2 2
8 2 8 4 3
2 4 6 4 5
10 3 10 4 8
12 3 12 4 13
2 2 4 2 21
 3

อ่านตัวอย่างแรก: ตารางกว้าง 6 ช่องตามแกน x สูง 9 ช่องตามแกน y งบ 42 มี 5 ก้อน บรรทัด 4 1 6 3 12 คือก้อนที่คลุมช่อง (4, 1) ถึง (6, 3) ค่ารื้อ 12

ใบ้

ตารางใหญ่ได้ถึงล้านคูณล้าน เราแตะทุกช่องไม่ได้ แต่สิ่งกีดขวางมีแค่ไม่กี่แสนก้อน ข้อมูลจริงที่มีอยู่น้อยกว่าตารางมหาศาล

ลองถามว่า ถ้ารู้ว่าจัตุรัสด้าน s วางได้ แล้วจัตุรัสด้าน s − 1 วางได้ไหม และถ้าคิดกลับด้าน มองว่ามุมล่างซ้ายของจัตุรัสวางได้ที่ไหนบ้าง สิ่งกีดขวางหนึ่งก้อนจะห้ามมุมล่างซ้ายไว้ที่บริเวณรูปอะไร

ลองเอง · หาที่วางฐานให้ใหญ่ที่สุดในงบ

ตารางเดียวกับตัวอย่างแรกของโจทย์ งบ 42

ด้านยาว 1

คลิกช่องเพื่อวางมุมล่างซ้ายของฐาน แล้วปรับด้านยาว ตัวเลขในช่องคือค่ารื้อรวมของก้อนที่ทับช่องนั้น

ต้องจ่าย 0 จากงบ 0 · ใหญ่ที่สุดที่วางได้แล้ว 0

ก้อนหนึ่งก้อนคิดเงินครั้งเดียว ไม่ว่าฐานจะทับมันกี่ช่องก็ตาม

ลองเลื่อนฐานทีละช่องแล้วดูว่าค่าใช้จ่ายเปลี่ยนตอนไหน ค่าจะนิ่งอยู่จนกว่าขอบของฐานจะข้ามขอบของก้อนสักก้อน

เฉลย ตอนที่ 1 · วิธีช้าแต่ถูก ลองทุกขนาด ทุกมุม

เริ่มจากวิธีที่ตรงกับโจทย์ที่สุด ไล่ทุกด้านยาว s ทุกมุมล่างซ้าย (x, y) แล้วรวมค่ารื้อของก้อนที่ทับฐาน ก้อนไหนทับก็คิดเงินครั้งเดียว

ก้อนทับฐานเมื่อทั้งสองเหลื่อมกันทั้งแนวนอนและแนวตั้ง ภาพข้างล่างคือผลของวิธีนี้บนตัวอย่างแรก

1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 12 9 24 21 20 ฐานด้าน 4 มุม (1, 4) รื้อ 33 งบ 42 ทองคือกีดขวาง แดงคือก้อนที่ต้องรื้อ
ตัวอย่างแรก กว้าง 6 ยาว 9 งบ 42 ตัวเลขในก้อนคือค่ารื้อ กรอบเขียวคือฐานด้าน 4 ที่มุม (1, 4) ก้อนสีแดงคือก้อนที่ต้องรื้อ รวม 33 ไม่เกินงบ ส่วนด้าน 5 มุมที่ถูกที่สุดยังต้องจ่าย 45 (วาดประกอบโดยผู้เขียน)

วิธีนี้ถูกแน่นอน และหน้านี้ใช้มันเป็นตัวตรวจของทุกวิธีที่ตามมา ปัญหาอยู่ที่ปริมาณงาน

ลองคูณที่ขอบเขตเต็ม

  • ด้านยาว s มีได้ตั้งแต่ 1 ถึง 10⁶
  • ด้าน s มีมุมให้ลอง (M − s + 1)(N − s + 1) มุม รวมทุกด้านเท่ากับ 1² + 2² + … + M² ≈ M³/3 ≈ 3.3 × 10¹⁷ มุม
  • แต่ละมุมเช็กก้อน 400,000 ก้อน รวมราว 1.3 × 10²³ ครั้ง

เครื่องทั่วไปทำงานง่าย ๆ ได้ราว 10⁸ ครั้งต่อวินาที (กะคร่าว ๆ) ใน 5 วินาทีได้ราว 5 × 10⁸ ครั้ง วิธีนี้ช้ากว่างบราว 2.7 × 10¹⁴ เท่า

งานก้อนนี้คือจำนวนขนาด คูณจำนวนมุม คูณจำนวนก้อน ตอนต่อ ๆ ไปลดทีละตัว และชุดทดสอบย่อยแต่ละชุดเปิดทางให้ลดคนละแบบ

ชุดทดสอบย่อยของโจทย์ (ทุกชุด M, N ≤ 1,000,000)
ชุดคะแนนงบจำนวนก้อน
135B = 01 ≤ P ≤ 1,000
2350 < B ≤ 2,000,000,0001 ≤ P ≤ 30,000
330B = 01 ≤ P ≤ 400,000
ชุดที่ 1 กับ 3 งบเป็นศูนย์ทั้งคู่ ต่างกันที่จำนวนก้อน ชุดที่ 2 มีงบจริงแต่ก้อนน้อยกว่าชุดที่ 3 ราว 13 เท่า

เฉลย ตอนที่ 2 · ถามว่าขนาดนี้วางได้ไหม แทนการถามว่าใหญ่สุดเท่าไร

ตัวที่ลดง่ายที่สุดคือจำนวนขนาด ลองดูว่าถ้ารู้แล้วว่าด้าน s วางได้ เราบอกอะไรเกี่ยวกับด้านที่สั้นกว่าได้บ้าง

เอาฐานด้าน s − 1 ไปวางที่มุมเดียวกับฐานด้าน s ตัวเล็กอยู่ข้างในตัวใหญ่ทั้งตัว ก้อนไหนทับตัวเล็กก็ทับตัวใหญ่ด้วย ค่ารื้อของตัวเล็กเลยไม่เกินตัวใหญ่

ด้าน 4 ค่ารื้อ 33 ด้าน 3 ค่ารื้อ 33 มุมเดียวกัน (1, 4)
ตัวอย่างแรก ฐานสองขนาดที่มุม (1, 4) เดียวกัน กรอบเขียวด้าน 4 ค่ารื้อ 33 กรอบฟ้าด้าน 3 ค่ารื้อ 33 ตัวเล็กอยู่ข้างในตัวใหญ่ ก้อนที่ทับตัวเล็กก็ทับตัวใหญ่ด้วย

ข้อสังเกตของตอนนี้

ถ้าด้าน s วางได้ ทุกด้านที่สั้นกว่าวางได้หมด คำตอบของคำถาม "วางได้ไหม" เรียงเป็น ได้ ได้ ... ได้ แล้วไม่ได้ไปตลอด

คำตอบที่เรียงแบบนี้ใช้การค้นหาคำตอบแบบไบนารี (binary search on the answer อ่านว่า "ไบนารีเสิร์ช") ได้ คือถามขนาดตรงกลางของช่วงที่ยังไม่รู้ ถ้าได้ก็ทิ้งครึ่งล่าง ถ้าไม่ได้ก็ทิ้งครึ่งบน

ช่วง 0 ถึง 1,000,000 หดเหลือค่าเดียวใน 20 รอบ เพราะหารครึ่ง 20 ครั้งก็เหลือไม่ถึงหนึ่ง ท่านี้มีบทปูพื้นแยกไว้ที่เซกเมนต์ทรีกับการค้นหาคำตอบแบบไบนารี

ตัวอย่างแรก · ค่าใช้จ่ายต่ำสุดของแต่ละขนาด (งบ 42)
ด้านยาวค่าใช้จ่ายต่ำสุดมุมล่างซ้ายที่ถูกที่สุดอยู่ในงบไหม
1 0 (1, 1) ได้
2 0 (1, 1) ได้
3 9 (4, 4) ได้
4 33 (1, 4) ได้
5 45 (1, 3) ไม่ได้
6 54 (1, 4) ไม่ได้
ค่าใช้จ่ายไม่ลดลงเลยเมื่อด้านยาวขึ้น คำตอบคือ 4 ซึ่งเป็นขนาดสุดท้ายที่ยังอยู่ในงบ ทุกตัวเลขมาจากการไล่ทุกตำแหน่งจริง
โครงชั้นนอก 
// s ใหญ่ขึ้น ค่าใช้จ่ายก็ไม่มีทางถูกลง เพราะจัตุรัสเล็กที่ซ้อนอยู่ข้างในย่อมชนก้อนไม่มากกว่า
// เงื่อนไข "มีที่วางได้" จึงเป็นจริงเรียงติดกันแล้วเท็จตลอด ค้นหาแบบไบนารีได้
ll lo = 0, hi = min(M, N);
while (lo < hi) {
    ll md = (lo + hi + 1) / 2;
    if (ok(md)) lo = md; else hi = md - 1;
}

เฉลย ตอนที่ 3 · ก้อนหนึ่งก้อนห้ามมุมเป็นสี่เหลี่ยมผืนเดียว

ที่มาของแนวคิดนี้

ไบนารีเหลือ 20 รอบก็จริง แต่ในแต่ละรอบยังต้องไล่มุมนับล้านล้าน ตารางใหญ่ขนาดนี้แตะทุกช่องไม่ได้ ในขณะที่ก้อนมีแค่หลักแสน อัลกอริทึมต้องเดินตามก้อนแทน

ผมเลยกลับคำถาม จากเดิมที่ถามว่า "ฐานที่มุมนี้ทับก้อนไหน" เป็น "ก้อนนี้ทับฐานที่มุมไหนบ้าง"

ตอนนี้ใช้ตารางเล็กชุดหนึ่ง (ชุดเดียวกับแท็บที่ 4 ของเกม) จะได้เห็นทุกตัวเลขในหน้าเดียว ตารางกว้าง 9 สูง 5 งบ 3 มี 4 ก้อน

  • ก้อน A: คอลัมน์ 1 ถึง 2 แถว 1 ถึง 5 ค่ารื้อ 5
  • ก้อน B: คอลัมน์ 4 ถึง 4 แถว 1 ถึง 2 ค่ารื้อ 3
  • ก้อน C: คอลัมน์ 5 ถึง 6 แถว 4 ถึง 5 ค่ารื้อ 4
  • ก้อน D: คอลัมน์ 8 ถึง 9 แถว 1 ถึง 3 ค่ารื้อ 6

ตรึงด้าน s = 3 มุมล่างซ้ายมี x ได้ 1 ถึง M − s + 1 = 7 และ y ได้ 1 ถึง N − s + 1 = 3 ถ้ามุมอยู่เลยกว่านี้ ฐานจะยื่นออกนอกตาราง

เริ่มจากก้อน C ในแนวนอน เลื่อนฐานจากซ้ายไปขวาแล้วดูว่าที่มุมไหนเริ่มทับ และที่มุมไหนเลิกทับ

1 2 3 4 5 6 7 8 9 ก้อน C มุม x = 2 ไม่ทับ มุม x = 3 ทับ มุม x = 6 ทับ มุม x = 7 ไม่ทับ
แนวนอนอย่างเดียว ก้อน C อยู่คอลัมน์ 5 ถึง 6 ฐานกว้าง 3 ช่อง มุม x = 2 ยังไม่ถึงก้อน มุม 3 เริ่มทับ มุม 6 ทับเป็นตำแหน่งสุดท้าย มุม 7 พ้นไปแล้ว

ฐานที่มุม x กินคอลัมน์ x ถึง x + s − 1 มันเริ่มทับเมื่อขอบขวา x + s − 1 แตะคอลัมน์แรกของก้อน คือ x = X1 − s + 1 = 5 − 3 + 1 = 3 และทับไปจนขอบซ้าย x ยังอยู่ที่คอลัมน์สุดท้ายของก้อน คือ x = X2 = 6

แนวตั้งของก้อน C แล้วนับให้ครบ

  • ก้อนอยู่แถว 4 ถึง 5 ฐานเริ่มทับที่ y = 4 − 3 + 1 = 2 และทับไปถึง y = 5
  • แต่มุม y สูงสุดแค่ 3 เลยตัดเหลือ y = 2 ถึง 3
  • แนวนอน 3 ถึง 6 ไม่เกิน 7 ไม่ต้องตัด

มุมที่ทับก้อน C คือกรอบ 4 × 2 = 8 มุม ไล่ตรวจทุกมุมด้วยวิธีของตอนที่ 1 ก็เจอ 8 มุมชุดเดียวกัน

สูตรทั่วไป

  • x อยู่ระหว่าง X1 − s + 1 ถึง X2
  • y อยู่ระหว่าง Y1 − s + 1 ถึง Y2
  • ทั้งสองแกนตัดให้อยู่ในช่วงมุมที่วางได้ คือ 1 ถึง M − s + 1 และ 1 ถึง N − s + 1

คำถามในคำใบ้ที่ว่าก้อนหนึ่งก้อนห้ามมุมล่างซ้ายไว้เป็นรูปอะไร คำตอบคือสี่เหลี่ยมผืนเดียว เพราะแต่ละแกนได้ช่วงต่อเนื่องหนึ่งช่วง

ตารางจริง กว้าง 9 ยาว 5 แผนที่ของมุม เมื่อ s = 3 123456789 12345 A 5 B 3 C 4 D 6 5 5 5 8 8 5 3 7 4 3 7 4 0 4 4 6 10 10 6 6 6 1234567 123
ซ้ายคือตารางจริง ขวาคือแผนที่ของมุมล่างซ้ายเมื่อ s = 3 ตัวเลขในแต่ละมุมคือค่ารื้อรวมถ้าวางฐานที่มุมนั้น กรอบประสีชมพูคือมุมที่ทับก้อน C วงเขียวคือมุม (3, 1) ที่ค่ารื้อ 3 ไม่เกินงบ 3 ตรงกับกรอบเขียวทางซ้าย

นึกภาพ

คิดว่าก้อนแต่ละก้อนเป็นด่านเก็บเงินที่ปักป้ายคลุมพื้นที่สี่เหลี่ยมบนแผนที่ของมุม ยืนอยู่ที่มุมไหน ก็จ่ายให้ทุกด่านที่ป้ายคลุมจุดนั้น ด่านละครั้ง

คำถาม "ด้าน s วางได้ไหม" เลยเท่ากับถามว่า บนแผนที่ของมุม มีจุดไหนที่ผลรวมของสี่เหลี่ยมที่คลุมอยู่ไม่เกินงบ

เฉลย ตอนที่ 4 · ชุดที่ 1 งบศูนย์ หาช่องว่างทีละคอลัมน์

งบเป็นศูนย์แปลว่าห้ามชนก้อนไหนเลย ผลรวมไม่มีความหมายแล้ว เหลือแค่ถามว่าบนแผนที่ของมุม มีจุดที่ไม่มีสี่เหลี่ยมผืนไหนคลุมหรือเปล่า

สมมติเจอมุมว่างสักจุด ลองเลื่อนมันไปทางซ้ายทีละคอลัมน์ ตราบที่ยังว่างก็เลื่อนต่อได้ มันจะหยุดได้สองแบบ

  • ชนขอบตาราง ที่ x = 1
  • คอลัมน์ทางซ้ายของมันอยู่ในสี่เหลี่ยมของก้อนหนึ่ง สี่เหลี่ยมนั้นจบที่ X2 คอลัมน์ว่างแรกถัดออกมาคือ x = X2 + 1

ถ้ามีมุมว่าง ก็ต้องมีมุมว่างที่ x เป็น 1 หรือ X2 + 1 ของสักก้อน x ที่ต้องลองมีไม่เกิน P + 1 ค่า ค่าที่เกิน M − s + 1 ทิ้งได้ เพราะฐานที่มุมนั้นล้นตาราง

  1. เก็บช่วง y ห้ามของก้อนที่คลุมคอลัมน์ x โดยตัดปลายบนไม่ให้เกิน N − s + 1
  2. เรียงช่วงตามจุดเริ่ม
  3. เดินจาก y = 1 ถ้าช่วงถัดไปเริ่มเลยตำแหน่งปัจจุบัน แปลว่าเจอช่องว่าง
  4. ไล่ครบทุกช่วงแล้วตำแหน่งปัจจุบันยังไม่เกิน N − s + 1 ก็มีช่องว่างเหนือช่วงสุดท้าย
  5. ไม่เจอเลยก็ลอง x ถัดไป

ต่อหนึ่งรอบของไบนารีมี x ไม่เกิน P + 1 ค่า แต่ละค่าเช็ก P ก้อนแล้วเรียงช่วงอีกราว P log₂ P ครั้ง ชุดที่ 1 รวมได้ราว 2.2 × 10⁸ ใช้เวลา 0.07 วินาที แต่ที่ P = 400,000 พุ่งไปราว 6.4 × 10¹³

ชุดที่ 2 ใช้ท่านี้ไม่ได้ตั้งแต่ต้น งบมากกว่าศูนย์ต้องหาค่าต่ำสุดของผลรวม ซึ่งการหาช่องว่างตอบให้ไม่ได้

ดูโค้ดของชุดทดสอบย่อยชุดแรก
pyramid_sub.cpp 
// เฉลยชุดทดสอบย่อยชุดแรก งบเป็นศูนย์ และสิ่งกีดขวางไม่เกิน 1,000 ก้อน (35 คะแนน)
// งบเป็นศูนย์แปลว่าห้ามชนก้อนไหนเลย คำถามจึงเหลือแค่ "มีที่ว่างขนาดนี้ไหม"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int P; ll M, N;
vector<ll> x1_, y1_, x2_, y2_;

bool ok(ll s) {
    if (M - s + 1 < 1 || N - s + 1 < 1) return false;
    const ll XH = M - s + 1, YH = N - s + 1;
    // มุมล่างซ้ายที่น่าลองมีแค่ 1 กับคอลัมน์ถัดจากขอบขวาของแต่ละก้อน
    vector<ll> xs{1};
    for (int i = 0; i < P; i++) { ll v = x2_[i] + 1; if (v <= XH) xs.push_back(v); }
    sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end());

    vector<pair<ll,ll>> bad;
    for (ll x : xs) {
        bad.clear();
        for (int i = 0; i < P; i++) {
            if (x + s - 1 < x1_[i] || x > x2_[i]) continue;          // ก้อนนี้ไม่ขวางที่คอลัมน์นี้
            ll lo = max(1LL, y1_[i] - s + 1), hi = min(YH, y2_[i]);
            if (lo <= hi) bad.push_back({lo, hi});
        }
        sort(bad.begin(), bad.end());
        ll cur = 1;                                                  // ไล่หาช่องว่างแรกที่ไม่มีใครทับ
        for (auto& [lo, hi] : bad) {
            if (lo > cur) break;
            cur = max(cur, hi + 1);
        }
        if (cur <= YH) return true;
    }
    return false;
}

int main() {
    ll B;
    scanf("%lld %lld %lld %d", &M, &N, &B, &P);
    x1_.resize(P); y1_.resize(P); x2_.resize(P); y2_.resize(P);
    for (int i = 0; i < P; i++) { ll c; scanf("%lld %lld %lld %lld %lld", &x1_[i], &y1_[i], &x2_[i], &y2_[i], &c); }
    ll lo = 0, hi = min(M, N);
    while (lo < hi) { ll md = (lo + hi + 1) / 2; if (ok(md)) lo = md; else hi = md - 1; }
    printf("%lld\n", lo);
}

เฉลย ตอนที่ 5 · ชุดที่ 2 กวาดเส้นไปตามแกน x

ที่มาของแนวคิดนี้

พอต้องหาค่าต่ำสุดของผลรวม ผมลองตรึงคอลัมน์ x ของแผนที่มุมไว้คอลัมน์เดียว สี่เหลี่ยมที่คลุมคอลัมน์นั้นแต่ละผืน คือการบวกค่าลงช่วงหนึ่งของ y เหลือแค่ทำให้คอลัมน์เลื่อนได้

การกวาดเส้น (sweep line อ่านว่า "สวีปไลน์") คือเดินเส้นตั้งจากซ้ายไปขวาบนแผนที่ของมุม แล้วเก็บค่าของคอลัมน์ที่เส้นอยู่ไว้ในโครงสร้างข้อมูลตัวเดียว สี่เหลี่ยมหนึ่งผืนสร้างเหตุการณ์สองครั้ง

  • เข้า ที่ขอบซ้ายของมัน บวกค่ารื้อลงช่วง y ของมัน
  • ออก ที่คอลัมน์ถัดจากขอบขวา ลบค่าเดิมออก ถ้าคอลัมน์นั้นเกิน M − s + 1 ไม่ต้องสร้างเหตุการณ์ออก เพราะเส้นไปไม่ถึง

ระหว่างสองเหตุการณ์ที่ติดกัน ค่าในคอลัมน์ไม่เปลี่ยน ถามค่าต่ำสุดแค่ที่ x ที่มีเหตุการณ์ก็พอ

ยกเว้น x = 1 ที่ต้องถามเสมอแม้ไม่มีเหตุการณ์ เพราะคอลัมน์ซ้ายสุดอาจว่างทั้งคอลัมน์ โค้ดเริ่มที่ cur = 1 แล้วกระโดดไปเหตุการณ์ถัดไปทีละครั้ง

ลองเดินด้าน 3 งบ 3 บนตารางของตอนที่ 3 ตัวเลขในคอลัมน์ที่ไฮไลต์คือค่ารื้อรวมของแต่ละ y ณ ตอนนั้น ส่วนว่าเก็บค่าพวกนี้ไว้ยังไง ตอนที่ 6 จะเปิดดู

แผนที่ของมุมเมื่อ s = 3 กว้าง 7 สูง 3 งบ 3

A B C D x 1x 2x 3x 4x 5x 6x 7 y 1y 2y 3
ขั้นxเกิดอะไรค่าที่ y = 1 ถึง 3น้อยสุด
1 1 A เข้า +5 5, 5, 5
2 1 ถามค่าน้อยสุด 5, 5, 5 5
3 2 B เข้า +3 8, 8, 5
4 2 ถามค่าน้อยสุด 8, 8, 5 5
5 3 C เข้า +4 8, 12, 9
6 3 A ออก −5 3, 7, 4
7 3 ถามค่าน้อยสุด 3, 7, 4 3

ด้าน 3 จบที่ x = 3 เพราะเจอมุมที่ค่ารื้อ 3 ไม่เกินงบ ส่วนด้าน 4 กวาดจนหมดเหตุการณ์ ค่าต่ำสุดที่เจอคือ 7 มากกว่างบ 3 คำตอบของตารางนี้คือ 3

เฉลย ตอนที่ 6 · ต้นไม้ที่ตอบค่าต่ำสุดของคอลัมน์

เครื่องเดินของตอนที่ 5 ต้องการสองคำสั่ง คือบวกค่าทั้งช่วง y และถามค่าต่ำสุดของทั้งคอลัมน์ โครงสร้างที่ทำทั้งสองอย่างได้เร็วคือเซกเมนต์ทรี (segment tree อ่านว่า "เซกเมนต์ทรี")

มันเป็นต้นไม้ที่แต่ละปมดูแลช่วงหนึ่งของ y ปมบนสุดเรียกว่ารากดูแลทั้งคอลัมน์ ปมล่างสุดเรียกว่าใบดูแลทีละแถว ปม i มีลูก 2i กับ 2i + 1

ต้นไม้ของตัวอย่างมี 4 ใบ คือใบละแถวสำหรับ y = 1 ถึง 3 และใบส่วนเกินอีก 1 ใบที่เติมให้จำนวนใบเป็นกำลังสอง ใบส่วนเกินตั้งเป็นอนันต์ (∞) ไว้ จะได้ไม่ชนะตอนหาค่าต่ำสุด

การบวกทั้งช่วงไม่ได้ไล่บวกทีละใบ มันวางป้ายไว้ที่ปมที่ช่วงของปมอยู่ในช่วงที่บวกทั้งหมด เช่นเหตุการณ์แรก A เข้า +5 ที่ y 1 ถึง 3 ป้ายไปอยู่ที่ปม 6 กับ 2 (y 3 และ y 1 ถึง 2)

เหตุการณ์ของตอนที่ 5 กับปมที่ได้ป้าย
เหตุการณ์ปมที่ได้ป้าย
A เข้า +5 ที่ y 1 ถึง 3ปม 6 (y 3), ปม 2 (y 1 ถึง 2)
B เข้า +3 ที่ y 1 ถึง 2ปม 2 (y 1 ถึง 2)
C เข้า +4 ที่ y 2 ถึง 3ปม 5 (y 2), ปม 6 (y 3)
A ออก −5 ที่ y 1 ถึง 3ปม 6 (y 3), ปม 2 (y 1 ถึง 2)
ปม 1 mn 3 · lz 0 ปม 2 mn 3 · lz 3 ปม 3 mn 4 · lz 0 ปม 4 mn 0 · lz 0 ปม 5 mn 4 · lz 4 ปม 6 mn 4 · lz 4 ปม 7 mn ∞ · lz 0 y = 1y = 2y = 3ใบส่วนเกิน
ต้นไม้หลังเหตุการณ์สุดท้ายของเครื่องเดิน ในแต่ละปม lz คือป้ายที่ค้างไว้ mn คือค่าต่ำสุดของช่วงนั้น ปมสีทองคือปมที่มีป้ายค้าง รากมี mn = 3 ตรงกับค่าต่ำสุดของคอลัมน์ [3, 7, 4]

สิ่งที่แต่ละปมจำ

  • lz[i]: ค่าที่บวกให้ทั้งช่วงของปมนี้แล้วค้างไว้ที่นี่ เรียกว่าป้ายค้าง (lazy)
  • mn[i] = min(mn[2i], mn[2i+1]) + lz[i]: ค่าต่ำสุดของช่วงนี้ คือค่าต่ำสุดของลูก บวกป้ายที่ค้างไว้กับทั้งช่วง

ที่ปม 2: mn[2] = min(0, 4) + 3 = 3

ค่าจริงของแถวหนึ่งคือค่าที่ใบบวกป้ายทุกอันบนทางขึ้นราก เช่นแถว y = 1 ได้ 0 + 3 + 0 = 3 ตรงกับคอลัมน์ [3, 7, 4] ของขั้นสุดท้ายในเครื่องเดิน

คำถามมีแค่ที่ราก และ mn ของทุกปมนับป้ายของตัวเองไว้แล้ว ป้ายเลยไม่ต้องถูกดันลงลูกเลย ถ้าต้องถามค่าของช่วงย่อยถึงจะต้องดัน รายละเอียดอยู่ในบทเซกเมนต์ทรี

ในโจทย์จริง แถว y มีได้ถึงล้าน แต่ค่าในคอลัมน์เปลี่ยนได้แค่ที่จุดเริ่มของช่วงและจุดถัดจากปลายช่วง โค้ดเก็บใบเฉพาะจุดเหล่านั้น ไม่เกิน 2P + 1 ใบ เรียกว่าการบีบพิกัด (coordinate compression)

ตัวอย่างนี้มีจุดแบบนั้น 3 จุด เท่ากับจำนวนแถวพอดี เลยไม่มีอะไรให้บีบ

ถ้าใบส่วนเกินถูกตั้งเป็นศูนย์แทนอนันต์ รากจะเห็นศูนย์เสมอ ผมพลาดจุดนี้จริง เรื่องเต็มอยู่ในส่วนโค้ดท้ายหน้า

ต่อหนึ่งรอบของไบนารีมี 2P เหตุการณ์ แต่ละครั้งแตะปมราว 4 log₂(2P + 1) ปม (วางป้ายสองฝั่ง แล้วคำนวณ mn ใหม่ตามทางขึ้นรากอีกสองสาย) ชุดที่ 2 ได้ราว 7.7 × 10⁷ ใช้เวลาไม่เกิน 0.31 วินาที

วิธีนี้ผ่านชุดที่ 1 ได้ด้วย เพราะงบศูนย์ก็เป็นกรณีหนึ่งของ "ค่าต่ำสุดไม่เกินงบ"

เฉลย ตอนที่ 7 · ชุดที่ 3 สองตัวชี้แทนการค้นหาแบบไบนารี

เรื่องจริงที่เกิดขึ้น

หน้านี้เวอร์ชันก่อนส่งโค้ดที่ใช้วิธีของตอนที่ 5 และ 6 กับทุกชุด และเขียนไว้ว่าใช้เวลา 3.8 วินาที ผมหาไม่เจอว่าตัวเลขนั้นวัดจากเครื่องไหนหรืออินพุตแบบไหน

ตอนเขียนใหม่ ผมวัดโค้ดเวอร์ชันนั้นซ้ำ 7 ครั้งกับอินพุตสุ่ม P = 400,000 งบศูนย์ ได้ 8.8 ถึง 11.8 วินาที เกินลิมิต 5 วินาทีทุกครั้ง ชุดงบศูนย์เลยเปลี่ยนไปใช้สองตัวชี้ ซึ่งใช้เวลาไม่เกิน 2.1 วินาทีกับอินพุตแบบเดียวกัน

งานของตอนที่ 6 ยังคูณด้วย 20 รอบของไบนารี และชุดที่ 3 มีก้อนมากกว่าชุดที่ 2 ราว 13 เท่า งานเลยทะลุงบ

วิธีที่ 1 (ตอนที่ 1)

ไล่ทุกมุม ทุกก้อน

ราว 8 × 10¹⁸ แม้หลังค้นไบนารีแล้ว

ตรงตามนิยามที่สุด ใช้ได้แค่ตารางจิ๋ว

ใช้เป็นตัวตรวจ

วิธีที่ 2 (ตอนที่ 4)

หาช่องว่างทีละคอลัมน์

ราว 6.4 × 10¹³

ลองแค่ x ที่ติดขอบขวาของก้อน ใช้ได้เฉพาะงบศูนย์

ผ่านชุดที่ 1

วิธีที่ 3 (ตอนที่ 5 และ 6)

ไบนารี + กวาดเส้น

ราว 1.3 × 10⁹ ใช้เวลา 8.8 ถึง 11.8 วินาที

ใช้ได้ทุกงบ แต่ทำซ้ำ 20 รอบ

ผ่านชุดที่ 1 และ 2

วิธีที่ 4 (ตอนนี้)

สองตัวชี้

ราว 6.7 × 10⁷ ใช้เวลาไม่เกิน 2.1 วินาที

ไม่ต้องเดาด้านยาว เดินรอบเดียว ใช้ได้เฉพาะงบศูนย์

ผ่านชุดที่ 1 และ 3 รวมกับวิธีที่ 3 ได้ 100 คะแนน

1 · ไล่ทุกมุม ทุกก้อน 8 × 10¹⁸ 2 · หาช่องว่างทีละคอลัมน์ 6.4 × 10¹³ 3 · ไบนารี + กวาดเส้น 1.3 × 10⁹ 4 · สองตัวชี้ 6.7 × 10⁷ งบ 5 วินาที ≈ 5 × 10⁸ 10⁶ 10⁹ 10¹² 10¹⁵ 10¹⁸
จำนวนครั้งที่แตะก้อนหรือปมของต้นไม้ตามที่โค้ดทำ ที่ P = 400,000 สเกลลอการิทึม (แต่ละขีดคูณพันเท่า) เส้นประคืองบเวลา 5 วินาทีแบบกะคร่าว ๆ ตัวนับนี้หยาบ ใช้ดูลำดับขนาดเท่านั้น

ตัวนับนี้บอกได้แค่ลำดับขนาด ตามตัวนับ วิธีที่ 3 เกินงบราว 2.6 เท่า ส่วนเวลาที่วัดได้เกินลิมิต 1.8 ถึง 2.4 เท่า

จุดที่ตัวนับพลาดชัดที่สุดคือวิธีที่ 4 มันนับได้ราว 6.7 × 10⁷ น้อยกว่าวิธีที่ 3 ในชุดที่ 2 (7.7 × 10⁷) แต่ใช้เวลานานกว่าราว 7 เท่า

ต้นไม้ของวิธีที่ 4 มีสี่อาร์เรย์รวมราว 64 เมกะไบต์ ส่วนต้นไม้ของชุดที่ 2 ใช้ราว 2 เมกะไบต์

ผมเดาว่าการแตะหน่วยความจำที่ใหญ่เกินแคช (หน่วยความจำเร็วที่อยู่ติดซีพียู) แพงกว่ามาก บวกกับการอ่านอินพุตสี่แสนบรรทัด แต่ยังไม่ได้วัดแยกว่าส่วนไหนกินเวลาเท่าไร

งบเป็นศูนย์อีกครั้ง ทำให้ใช้ท่าที่ไม่ต้องตรึงด้านยาวได้ คือสองตัวชี้ (two pointers) แทนที่จะเดาด้านแล้วถาม เราให้ช่วงคอลัมน์ l ถึง r ของฐานยืดหดเอง ความกว้างคือ r − l + 1

บทสองตัวชี้กับหน้าต่างเลื่อนอธิบายท่านี้ตั้งแต่ต้น

ตอนนี้กลับมาคิดบนตารางจริง ก้อนที่แตะช่วงคอลัมน์นี้ปิดแถวของมันทั้งหมด ฐานกว้าง r − l + 1 วางได้เมื่อมีแถวว่างติดกันยาวอย่างน้อยเท่าความกว้าง

วิธีเดิน

  1. ขยับ r ไปทีละคอลัมน์ ก้อนที่เริ่มที่คอลัมน์ r เข้ามาปิดแถวของมัน
  2. ถ้าแถวว่างยาวสุดสั้นกว่าความกว้าง ให้ขยับ l ทีละคอลัมน์ ก้อนที่จบที่คอลัมน์ l หลุดออกก่อนขยับ
  3. จดความกว้างที่ดีที่สุดไว้

ถ้าช่วง l ถึง r วางไม่ได้ ช่วง l ถึง r + 1 ก็วางไม่ได้ เพราะกว้างขึ้นแต่แถวว่างมีแต่จะลดลง l เลยเดินหน้าอย่างเดียว และทั้งสองตัวชี้เดินรวมกันไม่เกิน 2M ก้าว

ต้นไม้ของตอนนี้เป็นอีกต้นหนึ่ง คนละต้นกับตอนที่ 6 มันอยู่บนแถว y จริงทั้ง N แถวโดยไม่บีบพิกัด และแต่ละปมจำสี่อย่าง

  • cov: จำนวนก้อนที่คลุมทั้งช่วงของปม
  • pre และ suf: แถวว่างที่ติดขอบล่างและขอบบนของช่วงยาวเท่าไร
  • bst: แถวว่างติดกันยาวสุดในช่วง ค่าที่รากคือตัวเลขที่ข้อ 2 ของวิธีเดินถาม

ต่อค่าสองลูกที่ราก ตอน r = 4

ก้อนที่อยู่ในช่วงตอนนั้นคือ B แถวว่างคือ 3, 4, 5 ลูกซ้ายดูแลแถว 1 ถึง 3 ลูกขวาดูแลแถว 4 ถึง 5

  • ลูกซ้าย: pre 0 · suf 1 · bst 1 และลูกขวา: pre 2 · suf 2 · bst 2
  • pre ของราก = 0 (ลูกซ้ายว่างไม่เต็มช่วง ใช้ pre ของลูกซ้ายเลย)
  • suf ของราก = 2 + 1 = 3 (ลูกขวาว่างทั้งช่วง เลยต่อกับ suf ของลูกซ้าย)
  • bst ของราก = max(1, 2, 1 + 2) = 3 แถวว่างที่ยาวที่สุดคร่อมรอยต่อพอดี

ปมที่ cov มากกว่าศูนย์ไม่มีแถวว่างเลย ปมอื่นต่อค่าจากลูกแบบข้างบน ก้อนเข้าและออกที่ช่วงแถวเดิมเสมอ cov เลยไม่ต้องดันลงลูก เหมือนป้ายค้างของตอนที่ 6

ลองเดินกับตารางเดิม แต่ตั้งงบเป็น 0 (ห้ามแตะก้อน A ถึง D เลย) คำตอบของการไล่ทุกขนาดคือ 3

สองตัวชี้บนตาราง 9 × 5 งบ 0
rก้อนที่เข้าก้อนที่หลุดlแถวว่างยาวสุดกว้างดีที่สุด
1 A 2 0 0 0
2 A 3 5 0 0
3 3 5 1 1
4 B 3 3 2 2
5 C B 5 3 1 2
6 5 3 2 2
7 5 3 3 3
8 D C 7 2 2 3
9 8 2 2 3
แถวสีเขียวคือตอนที่ความกว้างที่ดีที่สุดเพิ่มขึ้น จบที่ 3 ตรงกับการไล่ทุกขนาด ความกว้าง 0 คือตอนที่ l เลย r ไปแล้ว
  1. r = 1 · A เข้า · แถวว่าง 0 สั้นกว่ากว้าง 1 ขยับ l จาก 1 เป็น 2 · ดีที่สุด 0
  2. r = 2 · แถวว่าง 0 สั้นกว่ากว้าง 1 ขยับ l จาก 2 เป็น 3 (A หลุด) · ดีที่สุด 0
  3. r = 3 · แถวว่าง 5 พอสำหรับกว้าง 1 · ดีที่สุด 1
  4. r = 4 · B เข้า · แถวว่าง 3 พอสำหรับกว้าง 2 · ดีที่สุด 2
  5. r = 5 · C เข้า · แถวว่าง 1 สั้นกว่ากว้าง 3 ขยับ l จาก 3 เป็น 5 (B หลุด) · ดีที่สุด 2
  6. r = 6 · แถวว่าง 3 พอสำหรับกว้าง 2 · ดีที่สุด 2
  7. r = 7 · แถวว่าง 3 พอสำหรับกว้าง 3 · ดีที่สุด 3
  8. r = 8 · D เข้า · แถวว่าง 0 สั้นกว่ากว้าง 4 ขยับ l จาก 5 เป็น 7 (C หลุด) · ดีที่สุด 3
  9. r = 9 · แถวว่าง 2 สั้นกว่ากว้าง 3 ขยับ l จาก 7 เป็น 8 · ดีที่สุด 3

ก้อนเข้าครั้งเดียวและออกครั้งเดียว ครั้งละแวะราว 4 log₂ N ปม รวมการสร้างต้นไม้และการเดิน r ล้านก้าวได้ราว 6.7 × 10⁷

โค้ดเต็มเลยแยกทางตามงบ งบศูนย์ใช้สองตัวชี้ (ชุดที่ 1 และ 3) งบมากกว่าศูนย์ใช้ไบนารีกับการกวาดเส้น (ชุดที่ 2 ซึ่งโจทย์รับประกันว่า P ไม่เกิน 30,000)

โค้ด C++ และสิ่งที่ตรวจแล้ว

ส่วนของโค้ดเต็ม กับตอนที่อธิบาย
ส่วนในโค้ดอธิบายไว้ที่
build, addตอนที่ 6 · ต้นไม้ค่าต่ำสุด ป้ายค้าง และใบส่วนเกินที่ต้องเป็นอนันต์
ok ส่วนผู้สมัครแกน yตอนที่ 6 · การบีบพิกัด
ok ส่วนเหตุการณ์แกน x และลูปกวาดตอนที่ 3 (สี่เหลี่ยมของมุม) และตอนที่ 5 (เข้า ออก ถามราก)
zpull, zadd, solveZeroตอนที่ 7 · สองตัวชี้กับต้นไม้แถวว่าง
mainตอนที่ 7 (แยกตามงบ) และตอนที่ 2 (ค้นหาแบบไบนารี)
ดูโค้ดเต็ม
pyramid.cpp 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int P; ll M,N,B;
vector<ll> X1,Y1,X2,Y2,C;
vector<int> byX1,byX2,byY1,byY2;

// ---------- งบมากกว่าศูนย์ (ชุดที่ 2): ค้นหาแบบไบนารี + กวาดเส้น ----------
int SZ; vector<ll> mn,lz;
const ll INF=(ll)4e18;
void build(int k){
    SZ=1; while(SZ<k) SZ<<=1;
    mn.assign(2*SZ,0); lz.assign(2*SZ,0);
    for(int i=k;i<SZ;i++) mn[SZ+i]=INF;             // ใบส่วนเกินต้องเป็นอนันต์ ไม่ใช่ศูนย์
    for(int i=SZ-1;i>=1;i--) mn[i]=min(mn[2*i],mn[2*i+1]);
}
// บวกทั้งช่วงแบบไล่จากใบขึ้นราก ไม่ใช้การเรียกซ้ำ เพราะรอบนี้ถูกเรียกหลายสิบล้านครั้ง
void add(int l,int r,ll v){
    int L=l+SZ, R=r+SZ+1, l0=L, r0=R-1;
    while(L<R){
        if(L&1){ mn[L]+=v; lz[L]+=v; L++; }
        if(R&1){ --R; mn[R]+=v; lz[R]+=v; }
        L>>=1; R>>=1;
    }
    for(int i=l0>>1;i>=1;i>>=1) mn[i]=min(mn[2*i],mn[2*i+1])+lz[i];
    for(int i=r0>>1;i>=1;i>>=1) mn[i]=min(mn[2*i],mn[2*i+1])+lz[i];
}
vector<ll> cand; vector<int> klOf,krOf;
vector<ll> evX; vector<int> evI; vector<char> evAdd;
bool ok(ll s){
    if(M-s+1<1||N-s+1<1) return false;
    const ll YH=N-s+1, XH=M-s+1;
    // ผู้สมัครแกน y  รวมสองสายที่เรียงอยู่แล้ว จึงไม่ต้องเรียงใหม่ทุกรอบ
    cand.clear(); cand.push_back(1);
    { size_t a=0,b=0; ll va,vb;
      auto nextA=[&](){ while(a<(size_t)P){ int i=byY1[a]; ll lo=max(1LL,Y1[i]-s+1), hi=min(YH,Y2[i]); a++; if(lo<=hi){ va=lo; return true; } } return false; };
      auto nextB=[&](){ while(b<(size_t)P){ int i=byY2[b]; ll lo=max(1LL,Y1[i]-s+1), hi=min(YH,Y2[i]); b++; if(lo<=hi&&hi+1<=YH){ vb=hi+1; return true; } } return false; };
      bool ha=nextA(), hb=nextB();
      while(ha||hb){ ll v; if(!hb||(ha&&va<=vb)){ v=va; ha=nextA(); } else { v=vb; hb=nextB(); }
        if(cand.back()!=v) cand.push_back(v); } }
    int K=(int)cand.size(); build(K);
    // ดัชนีขอบล่าง/ขอบบนของแต่ละก้อน หาแบบสองตัวชี้ เพราะทั้งสองสายเรียงมาแล้ว
    { size_t p=0; for(int t=0;t<P;t++){ int i=byY1[t]; ll lo=max(1LL,Y1[i]-s+1), hi=min(YH,Y2[i]); if(lo>hi){ klOf[i]=-1; continue; }
        while(p+1<cand.size()&&cand[p+1]<=lo) p++; while(cand[p]>lo&&p>0) p--; klOf[i]=(int)p; } }
    { size_t p=0; for(int t=0;t<P;t++){ int i=byY2[t]; ll lo=max(1LL,Y1[i]-s+1), hi=min(YH,Y2[i]); if(lo>hi){ krOf[i]=-1; continue; }
        while(p+1<cand.size()&&cand[p+1]<=hi) p++; krOf[i]=(int)p; } }
    // เหตุการณ์แกน x  สองสายเรียงอยู่แล้วเช่นกัน จึงแค่ผสาน
    evX.clear(); evI.clear(); evAdd.clear();
    { size_t a=0,b=0;
      auto valA=[&](size_t t){ int i=byX1[t]; return max(1LL,X1[i]-s+1); };
      auto valB=[&](size_t t){ int i=byX2[t]; return min(XH,X2[i])+1; };
      auto usable=[&](int i){ ll xl=max(1LL,X1[i]-s+1), xr=min(XH,X2[i]); return klOf[i]>=0 && xl<=xr; };
      while(a<(size_t)P||b<(size_t)P){
        bool takeA;
        if(a>=(size_t)P) takeA=false; else if(b>=(size_t)P) takeA=true; else takeA = valA(a)<=valB(b);
        if(takeA){ int i=byX1[a]; if(usable(i)){ evX.push_back(valA(a)); evI.push_back(i); evAdd.push_back(1);} a++; }
        else { int i=byX2[b]; ll v=valB(b); if(usable(i)&&v<=XH){ evX.push_back(v); evI.push_back(i); evAdd.push_back(0);} b++; }
      } }
    size_t e=0; ll cur=1;
    while(cur<=XH){
        while(e<evX.size()&&evX[e]<=cur){ int i=evI[e]; add(klOf[i],krOf[i], evAdd[e]?C[i]:-C[i]); e++; }
        if(mn[1]<=B) return true;
        cur = (e<evX.size()) ? evX[e] : XH+1;
    }
    return false;
}

// ---------- งบเป็นศูนย์ (ชุดที่ 1 และ 3): สองตัวชี้ ไม่ต้องค้นหาแบบไบนารี ----------
// ต้นไม้บนแถว y จริงทั้ง N แถว แต่ละปมจำว่ามีกี่ก้อนที่คลุมทั้งช่วงของปม (cov)
// แถวว่างติดกันยาวสุดในช่วง (bst) และแถวว่างที่ติดขอบล่าง (pre) กับขอบบน (suf)
vector<int> cov, pre, suf, bst;
void zpull(int k,int l,int r){
    if(cov[k]>0){ pre[k]=suf[k]=bst[k]=0; return; }       // ทั้งช่วงถูกคลุม ไม่มีแถวว่าง
    if(l==r){ pre[k]=suf[k]=bst[k]=1; return; }
    int m=(l+r)/2, a=2*k, b=2*k+1, la=m-l+1, lb=r-m;
    pre[k] = pre[a]==la ? la+pre[b] : pre[a];
    suf[k] = suf[b]==lb ? lb+suf[a] : suf[b];
    bst[k] = max({bst[a], bst[b], suf[a]+pre[b]});
}
void zbuild(int k,int l,int r){
    if(l<r){ int m=(l+r)/2; zbuild(2*k,l,m); zbuild(2*k+1,m+1,r); }
    zpull(k,l,r);
}
// ก้อนเข้าบวก 1 ออกลบ 1 ที่ช่วงแถวเดิมเสมอ จึงไม่ต้องดันค่า cov ลงลูก
void zadd(int k,int l,int r,int ql,int qr,int v){
    if(qr<l||r<ql) return;
    if(ql<=l&&r<=qr){ cov[k]+=v; zpull(k,l,r); return; }
    int m=(l+r)/2;
    zadd(2*k,l,m,ql,qr,v); zadd(2*k+1,m+1,r,ql,qr,v);
    zpull(k,l,r);
}
ll solveZero(){
    cov.assign(4*N,0); pre=suf=bst=cov; zbuild(1,1,(int)N);
    // ฐานกินคอลัมน์ l..r  ก้อนที่แตะช่วงนี้คือก้อนที่ X1 <= r และ X2 >= l
    size_t a=0,b=0; ll l=1, best=0;
    for(ll r=1;r<=M;r++){
        while(a<(size_t)P && X1[byX1[a]]==r){ int i=byX1[a++]; zadd(1,1,(int)N,(int)Y1[i],(int)Y2[i],1); }
        // แถวว่างยาวไม่พอกับความกว้าง r-l+1 ก็หดจากซ้าย ก้อนที่จบที่คอลัมน์ l หลุดออกจากช่วง
        while(bst[1] < r-l+1){
            while(b<(size_t)P && X2[byX2[b]]==l){ int i=byX2[b++]; zadd(1,1,(int)N,(int)Y1[i],(int)Y2[i],-1); }
            l++;
        }
        best=max(best,r-l+1);
    }
    return best;
}

int main(){
    if(scanf("%lld %lld",&M,&N)!=2) return 0;
    scanf("%lld",&B); scanf("%d",&P);
    X1.resize(P);Y1.resize(P);X2.resize(P);Y2.resize(P);C.resize(P);
    klOf.assign(P,-1); krOf.assign(P,-1);
    for(int i=0;i<P;i++) scanf("%lld %lld %lld %lld %lld",&X1[i],&Y1[i],&X2[i],&Y2[i],&C[i]);
    byX1.resize(P);byX2.resize(P);byY1.resize(P);byY2.resize(P);
    for(int i=0;i<P;i++) byX1[i]=byX2[i]=byY1[i]=byY2[i]=i;
    sort(byX1.begin(),byX1.end(),[](int a,int b){return X1[a]<X1[b];});
    sort(byX2.begin(),byX2.end(),[](int a,int b){return X2[a]<X2[b];});
    sort(byY1.begin(),byY1.end(),[](int a,int b){return Y1[a]<Y1[b];});
    sort(byY2.begin(),byY2.end(),[](int a,int b){return Y2[a]<Y2[b];});
    if(B==0){ printf("%lld\n",solveZero()); return 0; }
    // งบมากกว่าศูนย์ โจทย์รับประกันว่า P ไม่เกิน 30,000 ค้นหาคำตอบแบบไบนารีบนด้านยาว
    ll lo=0,hi=min(M,N);
    while(lo<hi){ ll md=(lo+hi+1)/2; if(ok(md)) lo=md; else hi=md-1; }
    printf("%lld\n",lo);
}
ตัวตรวจ และสิ่งที่ตรวจแล้ว

ตัวตรวจไล่ทุกขนาด ทุกมุม ทุกก้อน และไม่หยุดที่ขนาดแรกที่วางไม่ได้ มันไม่พึ่งข้อสังเกตของเฉลยเลยสักข้อ

brute.cpp 
// ตัวตรวจ: ไล่ทุกด้านยาว ทุกมุม ทุกก้อน ตรงตามนิยามของโจทย์
// ไม่ใช้ข้อสังเกตใดของเฉลยเลย ทั้งการค้นหาแบบไบนารี สี่เหลี่ยมของมุม และสองตัวชี้
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll M, N, B; int P;
    scanf("%lld %lld %lld %d", &M, &N, &B, &P);
    vector<array<ll,5>> o(P);
    for (auto& r : o) scanf("%lld %lld %lld %lld %lld", &r[0], &r[1], &r[2], &r[3], &r[4]);
    ll best = 0;
    for (ll s = 1; s <= min(M, N); s++) {                 // ถามทุกขนาด ไม่หยุดที่ขนาดแรกที่วางไม่ได้
        bool fit = false;
        for (ll x = 1; x + s - 1 <= M && !fit; x++)
            for (ll y = 1; y + s - 1 <= N && !fit; y++) {
                ll c = 0;
                for (auto& r : o)                          // ก้อนที่ทับฐานคิดเงินครั้งเดียว
                    if (x <= r[2] && x + s - 1 >= r[0] && y <= r[3] && y + s - 1 >= r[1]) c += r[4];
                if (c <= B) fit = true;
            }
        if (fit) best = s;
    }
    printf("%lld\n", best);
}
  • โค้ดเต็ม: ตอบตัวอย่างของโจทย์ถูกทั้งสองชุด และตรงกับตัวตรวจทั้ง 4,000 ชุดสุ่ม (ตารางไม่เกิน 9 × 9 ก้อนไม่เกิน 6 ก้อน ครึ่งหนึ่งงบศูนย์)
  • โค้ดชุดที่ 1: ตรงกับตัวตรวจทั้ง 2,000 ชุดสุ่มที่งบศูนย์
  • โค้ดที่ผิด (ใบส่วนเกินเป็นศูนย์ ซึ่งตอนนี้กระทบเฉพาะทางงบมากกว่าศูนย์): ตอบผิด 135 จาก 3,000 ชุดสุ่ม
  • เวลาทุกตัวในหน้านี้วัดบนโน้ตบุ๊ก Core i7-1355U ผ่าน WSL (Ubuntu 22.04, g++ 11.4 -O2) จากโค้ดที่ดึงออกมาจากหน้านี้ กับอินพุตสุ่มบนตาราง 1,000,000 × 1,000,000

ทั้งหมดนี้คือการตรวจบนตารางเล็กกับอินพุตสุ่ม ยังไม่ใช่การพิสูจน์ เหตุผลที่ทำให้ถูกอยู่ในตอนที่ 2 (ขนาดเล็กกว่าวางได้เสมอ) ตอนที่ 3 (สี่เหลี่ยมของมุม) และตอนที่ 7 (l ไม่ต้องถอย)

ดูโค้ดที่ผิด กับเคสที่จับมันได้

รอบแรกผมขยายเซกเมนต์ทรีขึ้นเป็นกำลังสองตามความเคยชิน แล้วเผลอตั้งใบทั้งต้นเป็นศูนย์ในคราวเดียว บรรทัดเดียวกันในโค้ดที่ถูกเขียนว่า mn[SZ+i]=INF

pyramid_wrong.cpp · ตัดมาเฉพาะส่วนที่ผิด 
const ll INF = (ll)4e18;
int SZ; vector<ll> mn, lz;

void build(int k){
    SZ = 1; while (SZ < k) SZ <<= 1;
    mn.assign(2 * SZ, 0); lz.assign(2 * SZ, 0);
    for (int i = k; i < SZ; i++) mn[SZ + i] = 0;   // <-- บักอยู่บรรทัดนี้ ใบส่วนเกินถูกปล่อยไว้ที่ศูนย์
    for (int i = SZ - 1; i >= 1; i--) mn[i] = min(mn[2 * i], mn[2 * i + 1]);
}

// ปลายทางที่บักโผล่ อยู่ในลูปกวาดเส้นของ ok()
if (mn[1] <= B) return true;   // ถ้าต้นไม้มีใบส่วนเกิน mn[1] เป็นศูนย์เสมอ บรรทัดนี้จึงตอบ true

ใบส่วนเกินไม่เคยถูกบวกอะไร เพราะช่วงที่บวกอยู่ในใบจริงเสมอ ถ้าจำนวนผู้สมัครไม่ใช่กำลังสอง ต้นไม้จะมีใบพวกนี้ รากเห็นศูนย์ทันที และรอบนั้นตอบว่าวางได้เสมอ

ตอนนั้นทุกชุดยังใช้วิธีของตอนที่ 5 และตัวอย่างสองชุดของโจทย์ผ่านทั้งคู่ รอบที่การค้นหาแบบไบนารีถามมีดังนี้

  • ตัวอย่างแรก: ด้าน 3 (ผู้สมัคร 5 จุด มีใบส่วนเกิน ของจริงวางได้) · ด้าน 5 (ผู้สมัคร 4 จุด ไม่มีใบส่วนเกิน ของจริงวางไม่ได้) · ด้าน 4 (ผู้สมัคร 4 จุด ไม่มีใบส่วนเกิน ของจริงวางได้)
  • ตัวอย่างที่สอง: ด้าน 3 (ผู้สมัคร 3 จุด มีใบส่วนเกิน ของจริงวางได้) · ด้าน 4 (ผู้สมัคร 1 จุด ไม่มีใบส่วนเกิน ของจริงวางไม่ได้)

ทุกรอบที่มีใบส่วนเกิน ของจริงก็วางได้อยู่แล้ว คำตอบที่ผิดเลยไม่โผล่ ตัวสุ่มเทียบจับได้ที่ชุดนี้

อินพุตที่ทำให้ตก · ตาราง 9 × 6 งบ 10 
9 6
10
6
2 5 4 5 8
4 4 7 5 3
6 2 9 6 8
4 4 4 6 9
7 6 7 6 5
4 6 7 6 4

ของจริงตอบ 3 โค้ดที่ผิดตอบ 4 ที่ด้าน 4 มุมที่ถูกที่สุดยังต้องจ่าย 11 เกินงบ 10 แต่ mn[1] รายงานศูนย์ การค้นหาแบบไบนารีเลยเชื่อว่าวางได้

ทดสอบตัวเอง และท่าที่ติดมือกลับไป

ถ้าคอลัมน์หนึ่งมีผู้สมัคร 5 จุด ต้นไม้ค่าต่ำสุดในโค้ดมีใบส่วนเกินกี่ใบ

โค้ดตั้ง SZ เป็นกำลังสองที่เล็กที่สุดที่ไม่น้อยกว่าจำนวนผู้สมัคร คือ 8 ใบส่วนเกินมี 8 − 5 = 3 ใบ และทั้งหมดต้องเป็นอนันต์

ถ้าโจทย์บังคับให้ฐานเป็นสี่เหลี่ยมผืนผ้าขนาด a × b ตายตัว ต้องเปลี่ยนอะไรบ้าง

สูตรมุมใช้ a กับแกน x และ b กับแกน y คือ X1 − a + 1 ถึง X2 และ Y1 − b + 1 ถึง Y2 ขนาดตายตัวแล้วไม่ต้องค้นหาแบบไบนารี กวาดเส้นรอบเดียวก็ได้คำตอบ

ทำไมสองตัวชี้ใช้กับงบมากกว่าศูนย์ตรง ๆ ไม่ได้

เมื่อมีงบ เราต้องรู้ผลรวมของก้อนที่ทับแถวช่วงหนึ่ง แต่ก้อนคิดเงินครั้งเดียวไม่ว่าทับกี่แถว ค่ารื้อเลยแยกเป็นค่าต่อแถวแล้วบวกกันไม่ได้ ต้องย้ายไปคิดบนแผนที่ของมุม ซึ่งต้องตรึงด้านยาวไว้ก่อน

ท่าที่ยกไปข้ออื่นได้: เมื่อต้นทุนยังคูณจำนวนรอบของการค้นหาแบบไบนารีอยู่ ให้ดูว่ามีชุดทดสอบไหนที่ถามคำถามง่ายกว่า (ข้อนี้คือ "มีที่ว่างไหม") แล้วตอบมันในรอบเดียว

แหล่งที่มา

  1. โจทย์ Pyramid Base บน programming.in.th ข้อ 2013 programming.in.th/tasks/2013 (สืบค้น 6 กันยายน 2026)
  2. ต้นทางของโจทย์คือ 20th International Olympiad in Informatics ที่กรุงไคโร ประเทศอียิปต์ วันแข่งที่ 2