programming.in.th · ข้อ 2043

โศกนาฏกรรม: ขอบสี่ด้านของกรอบ บังคับปลายคู่ละข้างพอดี

นับคู่จุดที่ขึ้นทั้งสองแกนในกรอบสี่เหลี่ยม สองแสนกรอบภายในสี่วินาที เล่าตั้งแต่วิธีช้าที่สุดไปจนวิธีเต็ม มีเกมให้ลองเองก่อนเปิดเฉลย และเรื่องจริงของการไล่เวลาจาก 14.75 วินาทีเหลือ 3.66

★★★★★ offlineprefix sumBITcounting อ่าน 16 นาที เผยแพร่ 12 กันยายน 2026 อัปเดต 15 ตุลาคม 2026

โจทย์ · เหตุการณ์บนระนาบเวลา

ลองวาดประวัติศาสตร์ลงกระดาษ ให้เวลาเป็นแกนนอน ค่าของเหตุการณ์เป็นแกนตั้ง เหตุการณ์หนึ่งก็เป็นจุดหนึ่งจุด และยุคสมัยหนึ่งก็เป็นกรอบสี่เหลี่ยมหนึ่งกรอบ

เหตุการณ์มี N เหตุการณ์ เหตุการณ์ที่ i อยู่ที่จุด (i, P_i) โดย P เป็นการเรียงสับเปลี่ยนของ 1 ถึง N ไม่มีสองเหตุการณ์ไหนอยู่แถวหรือหลักเดียวกัน

คู่ i กับ j นับเป็นโศกนาฏกรรมเมื่อ i มาก่อน j และค่าของ i น้อยกว่าค่าของ j พูดง่าย ๆ คือจุดหนึ่งอยู่ล่างซ้ายของอีกจุด แต่ละยุคถามว่าในกรอบของยุคนั้นมีกี่คู่

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

อินพุต: บรรทัดแรก N M บรรทัดที่สองคือ P ทั้ง N ตัว แล้วอีก M บรรทัดคือกรอบของแต่ละยุค เขียนเรียงเป็น r1 r2 c1 c2
ขอบเขต: N ≤ 100,000, M ≤ 200,000, เวลา 4 วินาที หน่วยความจำ 1024 เมกะไบต์
เอาต์พุต: M บรรทัด บรรทัดละหนึ่งจำนวน คือจำนวนคู่ของยุคนั้น

EXAMPLE
Input	Output
9 9 9 8 7 6 2 4 5 3 1 4 9 3 6 2 9 1 8 3 8 2 4 3 9 2 7 2 8 1 6 1 9 1 9 1 3 5 7 2 3 3 3 6 6 6 6	1 4 2 4 4 4 0 0 0

อ่านตัวอย่างนี้ยังไง

บรรทัดแรก: จำนวนเหตุการณ์ กับจำนวนยุค
บรรทัดที่สอง: ค่าของแต่ละเหตุการณ์เรียงตามเวลา เช่นเหตุการณ์ที่ 5 มีค่า 2 จึงเป็นจุด (5, 2)
อีก 9 บรรทัด: กรอบของแต่ละยุค ช่วงดัชนีมาก่อน แล้วค่อยช่วงค่า

เอาต์พุตคือจำนวนคู่ในกรอบ ไม่ใช่จำนวนเหตุการณ์ในกรอบ

ยุคที่ 1 กรอบคือ 4 9 3 6 คือดัชนี 4 ถึง 9 และค่า 3 ถึง 6 ในกรอบมี 4 เหตุการณ์ คือ (4, 6), (6, 4), (7, 5), (8, 3)

แต่คำตอบคือ 1 เพราะมีคู่เดียวที่ขึ้นทั้งสองแกน คือ (6, 7) (P₆ = 4 น้อยกว่า P₇ = 5) คู่อื่นค่าลดลงหมด

ยุคที่ 2 ตอบ 4 จากคู่ (5, 6), (5, 7), (5, 8), (6, 7) ส่วนสามยุคท้ายตอบ 0 เพราะกรอบแคบจนเหลือเหตุการณ์ไม่ถึงสองอัน

ตัวอย่างนี้ยังช่วยเช็กว่าอ่านโจทย์ถูก ถ้าเผลอนับคู่ที่ค่าลดลง ยุคที่ 1 จะได้ 5 ถ้าเผลอสลับช่วงดัชนีกับช่วงค่า จะได้ 0 ไม่ตรงกับ 1 ทั้งคู่

ตัวอย่างทั้ง 9 เหตุการณ์ กรอบทองคือยุคที่ 1 จุดทึบคือเหตุการณ์ที่อยู่ในกรอบ 4 จุด เส้นเขียวคือคู่เดียวที่ขึ้นทั้งสองแกน

ใบ้

ถ้ากรอบเดียวก็ไล่ทุกคู่ในกรอบจบ แต่มี 200,000 กรอบ และแต่ละกรอบอาจกิน 100,000 เหตุการณ์ คูณกันแล้วเกินงบไปมหาศาล

ลองสังเกตอย่างหนึ่งก่อน คู่ที่เรานับมีเงื่อนไขติดตัวอยู่แล้วสองข้อคือ i มาก่อน j และค่าของ i น้อยกว่าค่าของ j แล้วกรอบมีขอบสี่ด้าน ขอบทั้งสี่ด้านนั้นบังคับปลายทั้งสองข้างจริง ๆ หรือเปล่า

ลองเอง · หาโศกนาฏกรรมให้ครบทุกคู่

กรอบกินทั้งกระดาน อุ่นเครื่องก่อน

กดจุดสองจุดเพื่อเลือกหนึ่งคู่

กรอบทองคือยุคที่ถาม วงที่ขอบทองคือเหตุการณ์ที่อยู่ในกรอบ กดสองจุดเพื่อเสนอหนึ่งคู่

เกมที่สองถามเรื่องที่เฉลยต้องใช้: ถ้าค่อย ๆ หดกรอบเข้ามาทีละด้าน คู่จะหลุดเพราะปลายไหน

มีคู่เดียวบนกระดาน หดขอบไหนก็ได้ แล้วดูว่าตอนคู่หลุด ปลายไหนออกนอกกรอบก่อน

ขอบซ้าย (r1)

ขอบขวา (r2)

ขอบล่าง (c1)

ขอบบน (c2)

คู่นี้อยู่ในกรอบครบทั้งสองปลาย ยังนับได้

ตอนคู่หลุด ปลายไหนออกนอกกรอบ
ขอบที่หด	ปลายล่าง i	ปลายบน j
ขอบซ้าย (r1)	·	·
ขอบขวา (r2)	·	·
ขอบล่าง (c1)	·	·
ขอบบน (c2)	·	·

ลองหดครบสี่ขอบ ให้คู่หลุดด้วยแต่ละขอบอย่างน้อยครั้งหนึ่ง

ลองเล่นดูก่อนนะครับ พอเห็นว่าคู่แบบไหนถึงนับได้ และขอบไหนไล่ปลายไหนออก ค่อยไปดูเฉลย

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

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

ผมไม่ได้นึกท่าออกตั้งแต่แรก เริ่มจากวิธีที่ตรงที่สุดก่อน แล้วคูณดูว่าช้ากว่างบกี่เท่า ตัวเลขนั้นบอกเองว่าต้องไปหาท่าแบบไหน

ไล่จากช้าไปเร็ว มีสามขั้น ขั้นที่สองใช้ BIT (ต้นไม้เฟนวิก) ซึ่งเป็นตัวนับที่ตอบว่า "ที่จดไว้มีกี่ตัวที่ค่าไม่เกิน v" ได้ในราว log N ก้าว อธิบายเต็มอยู่ที่หน้าผลรวมสะสมกับต้นไม้เฟนวิก

วิธีที่ 1

ไล่ทุกคู่ในกรอบ

ราว N² ต่อคำถาม

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

ได้ชุด N, M ≤ 10

วิธีที่ 2

เดินตามดัชนี + BIT

ราว (r2 − r1) × log N

เดินจาก r1 ไป r2 จดลง BIT เฉพาะตัวที่ค่าอยู่ใน [c1, c2] แต่ละตัวค่า v ถามว่าที่จดไว้มีกี่ตัวค่าอยู่ใน [c1, v − 1]

ได้ชุด N, M ≤ 5,000

วิธีเต็ม

แบ่งราก

ราว √N ต่อคำถาม (เศษบวก log)

หั่นเป็นก้อน (sqrt decomposition) ก้อนที่อยู่ในกรอบเต็ม ๆ ตอบจากตารางที่เตรียมไว้ เศษที่ขอบไล่เอง เล่าในตอนที่ 2 ถึง 5

ได้ครบ 100 คะแนน

จำนวนก้าวที่ขอบเขตเต็ม สเกลแบบ log (ขีดละพันเท่า) เส้นทองคืองบ 4 วินาที โดยคิดหยาบ ๆ ว่าเครื่องทำได้ราว 10⁸ ก้าวต่อวินาที แท่งแบ่งรากคิดจากต้นทุนจริงราว 1,710 ก้าวต่อคำถาม (ดูตอนที่ 3)

วิธีที่ 2 ที่ขอบเขตเต็มคือ 200,000 × 100,000 × 17 ≈ 340,000,000,000 ก้าว เกินงบราว 850 เท่า ปรับนิดหน่อยไม่พอแน่

คิดกลับด้านจากงบแทน ถ้าคำถามละใช้แค่ √N ≈ 316 ก้าว ทั้งหมดรวมราว 63 ล้านก้าว ต่อให้คูณค่าคงที่เข้าไปอีกหลายเท่าก็ยังทัน เป้าจึงชัดว่าต้องตอบข้อละราว √N

ชุดคะแนนของโจทย์
คะแนน	เงื่อนไขของชุด
12	N, M ไม่เกิน 10
12	N, M ไม่เกิน 3000 ถึง 5000 (สามชั้น ชั้นละ 4%)
16	c1 = 1 และ c2 = N คือไม่มีขอบค่า (สี่ชั้น)
12	กรอบสองอันซ้อนกันสนิทหรือไม่แตะกันเลย (สามชั้น)
24	N ไม่เกิน 20000 ถึง 70000 (หกชั้น)
12	ทั้งลำดับมีคู่ที่ไม่เพิ่มขึ้นไม่เกิน 50 คู่
12	ไม่มีเงื่อนไขเพิ่ม

สองแถวแรกได้จากวิธีที่ 1 กับ 2 แถว c1 = 1 และแถวคู่ไม่เพิ่มขึ้นไม่เกิน 50 คู่มีทางลัดของตัวเอง (หน้านี้ไม่ได้เล่า) ที่เหลือต้องใช้วิธีเต็ม

ก่อนลงมือหั่น มีเรื่องหนึ่งที่ทำให้งานหั่นง่ายลงครึ่งหนึ่ง จำเกมหดกรอบเมื่อกี้ได้ไหม

เฉลย ตอนที่ 2 · ขอบสี่ด้านบังคับปลายละข้าง

คู่หนึ่งมีสองจุด เรียกจุดที่มาก่อนว่าปลายล่าง (i) เพราะค่าน้อยกว่าด้วย จึงอยู่ล่างซ้าย อีกจุดคือปลายบน (j) อยู่บนขวา

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

แปดเงื่อนไข เหลือของจริงสี่ข้อ
เงื่อนไข	ผล
i ≥ r1	ต้องเช็ก
i ≤ r2	ฟรี เพราะ i < j ≤ r2
j ≥ r1	ฟรี เพราะ j > i ≥ r1
j ≤ r2	ต้องเช็ก
P_i ≥ c1	ต้องเช็ก
P_i ≤ c2	ฟรี เพราะ P_i < P_j ≤ c2
P_j ≥ c1	ฟรี เพราะ P_j > P_i ≥ c1
P_j ≤ c2	ต้องเช็ก

ข้อที่ฟรีมาจากเหตุผลเดียวกันหมด คือ i มาก่อน j และค่าของ i น้อยกว่าค่าของ j อยู่แล้ว ถ้า j ยังไม่เกิน r2 จุด i ที่มาก่อนก็ไม่เกินแน่นอน

ขอบซ้ายกับขอบล่าง (สีทอง) ดูแลแค่ปลายล่าง ขอบขวากับขอบบน (สีเขียว) ดูแลแค่ปลายบน

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

เฉลย ตอนที่ 3 · หั่นเป็นบล็อก แล้วแยกคู่ตามท่อนที่ปลายตก

หั่นแกนดัชนีเป็นบล็อกละ B ตำแหน่ง โดยให้ B ราว √N (ที่ขอบเขตเต็มโค้ดใช้ B = 139) ช่วง [r1, r2] ของคำถามหนึ่งจะเห็นเป็นสามท่อนแบบในรูป

ตัวอย่างบล็อกละ 4 ตำแหน่ง ช่วง [r1, r2] แตกเป็นเศษซ้าย บล็อกเต็มตรงกลาง และเศษขวา เศษแต่ละฝั่งยาวไม่เกิน B

ต่อจากนี้จนจบตอนที่ 4 ใช้ตัวอย่างเดียวกันตลอด: 12 ตำแหน่ง บล็อกละ 3 (รูปบนใช้บล็อกละ 4 แค่ให้เห็นภาพ) ค่าเรียงตามตำแหน่งคือ 7, 11, 1, 2, 9, 5, 6, 3, 10, 12, 4, 8

บล็อก 0 (ตำแหน่ง 1 ถึง 3): ค่า 7, 11, 1
บล็อก 1 (ตำแหน่ง 4 ถึง 6): ค่า 2, 9, 5
บล็อก 2 (ตำแหน่ง 7 ถึง 9): ค่า 6, 3, 10
บล็อก 3 (ตำแหน่ง 10 ถึง 12): ค่า 12, 4, 8

เครื่องมือแรกคือตาราง F[v][b] = จำนวนตำแหน่งในบล็อก 0 ถึง b − 1 ที่ค่าไม่เกิน v เป็นผลรวมสะสมทั้งตามค่าและตามบล็อก

ตาราง F ของตัวอย่าง
v	b = 1	b = 2	b = 3	b = 4
0	0	0	0	0
1	1	1	1	1
2	1	2	2	2
3	1	2	3	3
4	1	2	3	4
5	1	3	4	5
6	1	3	5	6
7	2	4	6	7
8	2	4	6	8
9	2	5	7	9
10	2	5	8	10
11	3	6	9	11
12	3	6	9	12

คอลัมน์ b = 0 เป็นศูนย์ตลอดเพราะยังไม่มีบล็อกไหนอยู่ก่อนบล็อก 0 ช่องทองคือสี่ช่องที่ตัวอย่างข้างล่างใช้

ลองอ่าน F

บล็อก 1 ถึง 2 มีกี่ตัวที่ค่าอยู่ใน [4, 10]

(F[10][3] − F[10][1]) − (F[3][3] − F[3][1])
= (8 − 2) − (3 − 1) = 4 ตัว คือค่า 9, 5, 6, 10

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

สี่แบบของคู่ กับวิธีนับแต่ละแบบ
ปลายสองข้างอยู่ตรงไหน	นับยังไง
เศษทั้งคู่ (ซ้ายกับซ้าย ขวากับขวา หรือซ้ายกับขวา)	ชิ้นเศษรวมไม่เกิน 2B ตัว แต่ละบล็อกเรียงค่าไว้ล่วงหน้าแล้ว จึงดึงเศษออกมาเรียงตามค่าได้เลย แล้วนับด้วย BIT แบบวิธีที่ 2 ราว B log B ก้าว
ข้างหนึ่งเป็นเศษ อีกข้างอยู่ในบล็อกเต็ม	ต่อชิ้นเศษหนึ่งชิ้น บวกลบสี่ช่องของ F ถ้าเศษซ้ายค่า v เป็นปลายล่าง นับตัวในบล็อกเต็มที่ค่าอยู่ใน [v + 1, c2] ถ้าเศษขวาค่า v เป็นปลายบน นับที่ค่าอยู่ใน [c1, v − 1]
ในบล็อกเต็มบล็อกเดียวกัน	อ่านตาราง f ของบล็อกนั้น (ข้างล่าง) ครั้งเดียวต่อบล็อก
ในบล็อกเต็มคนละบล็อก	ยากที่สุด แยกไปเล่าในตอนที่ 4

ที่ขอบเขตเต็ม เศษสองฝั่งรวมไม่เกิน 278 ตำแหน่ง และบล็อกเต็มมีไม่เกิน 720 บล็อก (100,000 ÷ 139)

ลองจัดหมวดเองบนแถบบล็อกละ 4 แบบในรูป กดสองช่องในช่วง [r1, r2] เป็นปลายล่างกับปลายบนของคู่หนึ่ง

บล็อก 0

บล็อก 1

บล็อก 2

บล็อก 3

บล็อก 4

บล็อก 5

กดช่องแรก

เจอแล้ว 0 จาก 4 แบบ

ตาราง f ใช้กับคู่ในบล็อกเดียวกัน เรียงค่าในบล็อกแล้วให้อันดับ 1 ถึง B แล้วเตรียมตาราง B × B ไว้ว่า ถ้าปลายล่างอันดับไม่ต่ำกว่า u และปลายบนอันดับไม่เกิน v จะมีกี่คู่ แค่สองเงื่อนไขนี้พอ เพราะตอนที่ 2 ตัดเหลือปลายละข้อแล้ว

แถบค่า [c1, c2] แปลงเป็นช่วงอันดับด้วย F เพราะอันดับเรียงตามค่า

ตัวที่ค่าไม่เกิน c2 ในบล็อก b คืออันดับ 1 ถึง F[c2][b + 1] − F[c2][b] ตัวที่ค่าต่ำกว่า c1 คืออันดับ 1 ถึง F[c1 − 1][b + 1] − F[c1 − 1][b] ช่วงที่ต้องการคืออันดับระหว่างสองตัวเลขนี้

ทำไม B = 139 ไม่ใช่ √N = 316 พอดี

ต่อคำถามมีงานสองฝั่ง ฝั่งบล็อกเต็มราว N ÷ B ก้าว ฝั่งเศษราว B log B ก้าว บล็อกใหญ่ฝั่งแรกเบาลงแต่ฝั่งหลังหนักขึ้น

B = 316 รวมราว 2,941 ก้าว ส่วน B = 139 เหลือราว 720 + 990 = 1,710 ก้าว เพราะฝั่งเศษมี log ติดมา จุดคุ้มจึงเลื่อนมาทางบล็อกเล็ก ตาราง f ทุกบล็อกรวมกันใช้ราว N × B ≈ 13.9 ล้านช่อง ยังอยู่ในหน่วยความจำ

เฉลย ตอนที่ 4 · คู่ข้ามบล็อก ใส่ค่าทีละตัวจากน้อยไปมาก

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

วิธีตัดคือกวาดค่า (sweep อ่านว่า "สวีป" แปลว่ากวาด) ใส่เหตุการณ์ทีละตัวตามลำดับค่า 1, 2, 3, …

นึกภาพ

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

ตอนใส่ตัวที่อยู่บล็อก bx มันเป็นปลายบนให้ทุกตัวที่ใส่แล้วในบล็อกก่อน bx และ ณ เวลา t ใส่ไปแค่ค่า 1 ถึง t ขอบค่าบน c2 จึงได้มาฟรี แค่อ่านผลตอน t = c2

สองแสนคำถามใช้การกวาดรอบเดียวร่วมกัน วิธีคือเก็บคำถามทั้งหมดไว้ก่อนแล้วค่อยตอบ (เรียกว่าทำแบบออฟไลน์, offline)

แต่ละคำถามนัดอ่านผลสองจังหวะ ตอน t = c2 ได้คู่ที่ค่าไม่เกิน c2 และตอน t = c1 − 1 เอาไว้หักคู่ที่ค่าต่ำกว่า c1 ออก (ทำไมต้องหัก ดูหลังเครื่องเดิน)

ระหว่างกวาดเก็บของไว้สองอย่าง

colTotal[bx] จำนวนคู่ที่ปลายบนอยู่บล็อก bx และปลายล่างอยู่บล็อกใดก็ได้ที่มาก่อน
E[b1][bx] จำนวนคู่ที่ปลายบนอยู่บล็อก bx และปลายล่างอยู่บล็อกที่มาก่อน b1 คือพวกที่หลุดขอบซ้ายของคำถาม

ใส่ค่าหนึ่งตัวต้องอัปเดตคอลัมน์ bx ของ E ทุกแถว ราว N ÷ B ช่อง ทั้งการกวาดจึงราว 72,000,000 ครั้ง (สังเกตด้วยว่า colTotal[bx] เท่ากับ E[bx][bx] เสมอ โค้ดเก็บแยกไว้ให้อ่านง่าย)

อ่านคำตอบของบล็อกเต็ม b1 ถึง b2

บวก colTotal[bx] − E[b1][bx] ไล่ bx = b1 ถึง b2 (อ่านแถวเดียวของ E ติดกันรวดเดียว)

ลองเดินดูกับตัวอย่าง 12 ตำแหน่ง ค่าเรียงตามตำแหน่งคือ 7, 11, 1, 2, 9, 5, 6, 3, 10, 12, 4, 8 คำถามมีบล็อกเต็มคือ 1 ถึง 2 แถบค่า [4, 10]

ขั้น 0

ใส่ค่า 1 ถึง 12 ทีละตัว บล็อกละ 3 ตำแหน่ง

บล็อก	0			1 (เต็ม)			2 (เต็ม)			3
ตำแหน่ง	1	2	3	4	5	6	7	8	9	10	11	12
ค่าที่ใส่แล้ว	·	·	·	·	·	·	·	·	·	·	·	·

	บล็อก 0	บล็อก 1	บล็อก 2
ใส่แล้ว	0	0	0
colTotal	0	0	0
E[1]		0	0
E[2]			0
E[3]

ช่องว่างในแถว E คือช่องที่คำถามไม่เคยอ่าน แถว E[0] ไม่ได้วาดเพราะเป็นศูนย์ตลอด

ผลที่อ่านได้ตอน t = 10 คือ 6 คู่ ซึ่งยังรวมคู่ที่ค่าต่ำกว่าขอบล่าง 4 อยู่

ขอบล่างแก้ด้วยการแบ่งค่าเป็นสองกอง กอง A คือค่าที่น้อยกว่า c1 กอง S คือค่าใน [c1, c2] คู่ที่ค่าไม่เกิน c2 จึงมีสามพวก: ใน A ทั้งคู่, ใน S ทั้งคู่, และข้ามกอง เราต้องการแค่พวกที่สอง

แกนค่าของตัวอย่าง ค่าต่ำกว่า 4 คือกอง A ค่า 4 ถึง 10 คือกอง S คู่ที่ค่าไม่เกิน 10 มีสามพวกตามที่ปลายสองข้างตก

สูตรตัดขอบค่าล่าง

คู่ที่อยู่ใน S ทั้งคู่ = (ผลที่อ่านตอน t = c2) − (ผลที่อ่านตอน t = c1 − 1) − Cross(A, S)

ผลที่อ่านตอน t = c1 − 1 คือพวกใน A ทั้งคู่ ส่วน Cross(A, S) คือพวกข้ามกอง

Cross นับง่าย เพราะค่าทุกตัวใน A น้อยกว่าทุกตัวใน S ปลายล่างของคู่ข้ามกองจึงมาจาก A เสมอ

เหลือดูแค่ตำแหน่ง: ตัวใน S ที่บล็อก b จับคู่กับตัวใน A ทุกตัวในบล็อกเต็มก่อนหน้า (นับเฉพาะบล็อก b1 ถึง b − 1 เพราะปลายล่างต้องอยู่ในช่วงของคำถามด้วย) อ่านจำนวนจาก F ได้หมด

ในตัวอย่าง ตัวใน S ของบล็อก 2 (ค่า 6, 10) จับคู่กับตัวใน A ที่อยู่บล็อกก่อนหน้า (ค่า 2) ได้ 2 × 1 = 2 คู่ จึงได้ Cross = 2 คำตอบของแบบนี้คือ 6 − 1 − 2 = 3 คู่ ตรงกับการไล่นับตรง ๆ ทีละคู่

เฉลย ตอนที่ 5 · จาก 14.75 วินาที เหลือ 3.66 ส่วนใหญ่มาจากการวางข้อมูล

เรื่องจริงที่เกิดขึ้นตามลำดับ

ตัวแรกที่ให้คำตอบถูกทุกเคสใช้เวลา 14.75 วินาที จากลิมิต 4 วินาที คือช้ากว่าที่ต้องการเกือบสี่เท่า ตอนนั้นผมคิดว่าคงต้องรื้ออัลกอริทึม

ที่แก้จริงมีอย่างเดียวที่แตะอัลกอริทึม: เวอร์ชันแรกหาช่วงอันดับของแต่ละบล็อกด้วย binary search บนค่าที่เรียงไว้ ทุกบล็อกทุกคำถาม พอเปลี่ยนไปอ่านจาก F ตามที่เล่าในตอนที่ 3 log ตัวนั้นก็หายไป ที่เหลือทั้งหมดคือการวางข้อมูลในหน่วยความจำ

แคชคืออะไร

แคช (cache อ่านว่า "แคช" มาจากคำฝรั่งเศส cacher แปลว่าซ่อน) คือหน่วยความจำก้อนเล็กที่เร็วมาก ติดอยู่กับ CPU เทียบได้กับโต๊ะทำงาน ส่วน RAM คือโกดังหลังร้าน

ทุกครั้งที่ไปโกดัง CPU ยกของมาทั้งถาด ถาดละ 64 ไบต์ (int 16 ตัวที่อยู่ติดกัน) ของชิ้นถัดไปอยู่ถาดเดิมก็หยิบจากโต๊ะได้เลย ถ้าไม่อยู่ต้องเดินไปโกดังใหม่ ช้ากว่าเป็นสิบ ๆ เท่า

ตาราง F ผมเก็บเป็น F[บล็อก][ค่า] ตามที่นึกออกก่อน แต่ลูปที่รันบ่อยที่สุดไล่ทีละบล็อกโดยตรึงค่าไว้ การอ่านสองครั้งติดกันจึงห่างกัน 391 กิโลไบต์ ไม่เคยอยู่ถาดเดียวกัน

พอสลับเป็น F[ค่า][บล็อก] ลูปเดียวกันก็อ่านของที่วางติดกัน

แถวบน: อ่าน F ของบล็อก 0, 1, 2 ที่ค่าเดียวกัน แต่ละครั้งกระโดดข้ามทั้งแถว แถวล่าง: สลับแกนแล้ว ของที่อ่านอยู่ติดกัน หยิบมาในถาดเดียว

ไล่เวลาบนอินพุตชุดเดียวกัน ที่ N = 100,000, M = 200,000
แก้อะไร	วินาที
ตัวแรกที่ให้คำตอบถูก	14.75
ตัด binary search ต่อบล็อกต่อคำถาม ใช้ตาราง F แทน	8.14
สลับแกนตาราง F จาก F[บล็อก][ค่า] เป็น F[ค่า][บล็อก]	3.88
สลับแกนตาราง E กับตาราง f แล้วจูนขนาดบล็อกใหม่	3.66

เร็วขึ้น 4 เท่า แถวแรกตัด log ทิ้ง อีกสองแถวจำนวนคำสั่งแทบไม่เปลี่ยน แค่สลับแกนตาราง F ก็ลดไป 4.26 วินาที

เรื่องที่ผมไม่ได้คาดไว้คือขนาดบล็อกที่ดีที่สุดย้ายที่หลังแก้แคช ก่อนแก้ B = 240 ชนะ B = 120 พอแก้เสร็จกลับตรงข้าม B = 139 เร็วที่สุด ส่วน B = 80 ช้ากว่าราวหกสิบเปอร์เซ็นต์

บล็อกใหญ่เสียเปรียบเพราะตาราง f ของแต่ละบล็อกมีขนาด B × B ต้องเล็กพอให้ค้างอยู่บนโต๊ะได้ ส่วนบล็อกเล็กเกินไปก็มีจำนวนบล็อกเยอะ งานฝั่งบล็อกเต็มต่อคำถามกับการอัปเดต E จึงเพิ่มตาม ค่า B ที่จูนไว้ตอนข้อมูลยังวางผิดแกนจึงใช้ต่อไม่ได้

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

โค้ด

โค้ดเต็มแบ่งเป็นหกช่วง แต่ละช่วงมีคอมเมนต์หัวเป็นชื่อเดียวกับคอลัมน์แรก อ่านคู่กับเฉลยตอนที่ระบุได้เลย

แผนที่โค้ด
ช่วงในโค้ด	ทำอะไร	อ่านคู่กับ
อ่านอินพุต	อ่านทั้งไฟล์ทีเดียวแล้วแกะตัวเลขเอง	ตอนที่ 5
ตาราง F	นับว่าบล็อกก่อนหน้ามีกี่ตัวที่ค่าไม่เกิน v เก็บแบบ F[ค่า][บล็อก]	ตอนที่ 3, 5
ต่อบล็อก: เรียงค่า, อันดับ, ตาราง f	เตรียมคำตอบของคู่ในบล็อกเดียวกัน	ตอนที่ 3
อ่านคำถาม	เก็บกรอบของทุกคำถามไว้ก่อน เพราะการกวาดต้องรู้ล่วงหน้าว่าจะหยุดอ่านที่ค่าไหน	ตอนที่ 4
หมวด "บล็อกเต็มคนละบล็อก": กวาดค่าจากน้อยไปมาก	กวาดค่า เก็บ colTotal กับ E แล้วอ่านคำตอบตอน t = c2 และ c1 − 1	ตอนที่ 4
ประกอบคำตอบของแต่ละคำถาม (ก) ถึง (ง)	รวมสี่แบบของคู่ และหักส่วน Cross	ตอนที่ 2, 3, 4

ดูโค้ดเต็มขอบเขต

tears.cpp

// NOI 2020 "Tears" / โศกนาฏกรรม  (programming.in.th 2043, Luogu P6774)
// full constraints: N <= 1e5, M <= 2e5
//
// นับคู่ (i, j) ที่ i < j, P_i < P_j, ดัชนีทั้งคู่อยู่ใน [r1,r2], ค่าทั้งคู่อยู่ใน [c1,c2]
//
// ข้อสังเกตที่ใช้ตลอดไฟล์: คู่ที่นับมี i < j และ P_i < P_j อยู่แล้ว ขอบสี่ด้านจึงผูกปลายละข้าง
//     ดัชนีอยู่ใน [r1,r2] ทั้งคู่  <=>  i >= r1 และ j <= r2
//     ค่าอยู่ใน [c1,c2] ทั้งคู่    <=>  P_i >= c1 และ P_j <= c2
//
// หั่นแกนดัชนีเป็นบล็อกขนาด B แล้วแตกคำถามเป็นหกหมวดตามที่ปลายสองข้างตกอยู่
//   ซ้ายเศษ x ซ้ายเศษ, ขวาเศษ x ขวาเศษ, ซ้ายเศษ x ขวาเศษ   -> รวมเป็นรอบเดียว O(B log B)
//   ซ้ายเศษ x บล็อกเต็ม, บล็อกเต็ม x ขวาเศษ                 -> O(1) ต่อชิ้น ด้วยตาราง F
//   บล็อกเต็มบล็อกเดียวกัน                                    -> O(1) ต่อบล็อก ด้วยตาราง f ของบล็อกนั้น
//   บล็อกเต็มคนละบล็อก                                        -> กวาดค่า + ตาราง E (ดูด้านล่าง)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// อ่านอินพุตทั้งไฟล์ทีเดียวแล้วแกะเอง อินพุตเต็มขอบเขตมีตัวเลขราวเก้าแสนตัว
static char *inBuf; static size_t inPos, inLen;
static void readAll() {
    size_t cap = 1 << 22; inBuf = (char *)malloc(cap); inLen = 0;
    while (true) {
        if (inLen + (1 << 20) > cap) { cap <<= 1; inBuf = (char *)realloc(inBuf, cap); }
        size_t got = fread(inBuf + inLen, 1, 1 << 20, stdin);
        inLen += got;
        if (got < (1 << 20)) break;
    }
    inPos = 0;
}
static inline int readInt() {
    while (inPos < inLen && (inBuf[inPos] < '0' || inBuf[inPos] > '9')) inPos++;
    int x = 0;
    while (inPos < inLen && inBuf[inPos] >= '0' && inBuf[inPos] <= '9') x = x * 10 + (inBuf[inPos++] - '0');
    return x;
}

static int n, m, B, nb;
static vector<int> P, posOf;          // posOf[v] = ตำแหน่งของค่า v
static vector<int> blkOf, blkL, blkR;

// F[v][b] = จำนวนตำแหน่งในบล็อก 0..b-1 ที่มีค่า <= v   (b = 0..nb)
// เก็บโดยให้ "ค่า" เป็นแถว เพราะลูปร้อนทุกอันวิ่งตาม b โดยตรึง v ไว้
// เวอร์ชันแรกเก็บสลับกัน ทำให้ทุกการอ่านห่างกัน 400KB และพลาดแคชทุกครั้ง
static vector<int> F;                 // ขนาด (n+1) * (nb+1)
static int NBP1;
static inline int Fat(int b, int v) { return F[(size_t)v * NBP1 + b]; }
// จำนวนตำแหน่งในบล็อก [bl, br] ที่มีค่าอยู่ใน [lo, hi]
static inline int cntBlocks(int bl, int br, int lo, int hi) {
    if (bl > br || lo > hi) return 0;
    if (lo < 1) lo = 1;
    if (hi > n) hi = n;
    if (lo > hi) return 0;
    return (Fat(br + 1, hi) - Fat(bl, hi)) - (Fat(br + 1, lo - 1) - Fat(bl, lo - 1));
}

// ---- ต่อบล็อก: ค่าที่เรียงแล้ว, อันดับภายในบล็อก, และตาราง f ----
static vector<vector<int>> blkSortedPos;   // ตำแหน่งในบล็อก เรียงตามค่า
static vector<int> rankIn;                 // rankIn[pos] = อันดับของค่าที่ pos ภายในบล็อกของมัน (1-based)
static vector<vector<int>> fTab;           // fTab[b] = ตาราง (sz+1)^2 แบบผลรวมสะสมสองมิติ

// f[u][v] = จำนวนคู่ i<j ในบล็อกนี้ ที่ rank_i <= u, rank_j <= v และ rank_i < rank_j
// ผู้เรียกส่งอันดับมาให้เลย (คำนวณจากตาราง F ได้ในเวลาคงที่) จึงไม่ต้อง binary search
// เวอร์ชันแรกใช้ lower_bound/upper_bound ต่อบล็อกต่อคำถาม ซึ่งทำให้เคสช่วงยาวใช้เวลา 14.75 วินาที
static inline ll withinBlockRank(int b, int lo, int hi) {
    if (lo > hi) return 0;
    int W = blkR[b] - blkL[b] + 2;
    const int *f = fTab[b].data();
    // เก็บแบบ f[v][u] (แถวคือ v) การอ่านสองครั้งจึงอยู่แถวเดียวกัน ลด cache miss ครึ่งหนึ่ง
    const int *row = f + (size_t)hi * W;
    // #{rank_i >= lo, rank_j <= hi}  (rank_i < rank_j อยู่ในนิยามของ f แล้ว)
    return (ll)row[hi] - (ll)row[lo - 1];
}

int main() {
    // ---------- อ่านอินพุต ----------
    readAll();
    n = readInt(); m = readInt();
    P.assign(n + 2, 0); posOf.assign(n + 2, 0);
    for (int i = 1; i <= n; i++) { P[i] = readInt(); posOf[P[i]] = i; }

    // จูนแล้วที่ n = 1e5: B ราว 140 เร็วที่สุด (บล็อกเล็กลงทำให้ตาราง f ของแต่ละบล็อกอยู่ในแคชได้)
    B = max(1, (int)(sqrt((double)n) * 0.44));
    if (const char *e = getenv("BLK")) { int v = atoi(e); if (v > 0) B = v; }  // ใช้ตอนจูนเท่านั้น
    nb = (n + B - 1) / B;
    blkOf.assign(n + 2, 0); blkL.assign(nb, 0); blkR.assign(nb, 0);
    for (int i = 1; i <= n; i++) blkOf[i] = (i - 1) / B;
    for (int b = 0; b < nb; b++) { blkL[b] = b * B + 1; blkR[b] = min(n, (b + 1) * B); }

    // ---------- ตาราง F ----------
    NBP1 = nb + 1;
    F.assign((size_t)(n + 1) * NBP1, 0);
    for (int v = 1; v <= n; v++) {
        int *cur = &F[(size_t)v * NBP1];
        const int *prv = &F[(size_t)(v - 1) * NBP1];
        int bv = blkOf[posOf[v]];
        for (int b = 0; b <= bv; b++) cur[b] = prv[b];
        for (int b = bv + 1; b <= nb; b++) cur[b] = prv[b] + 1;
    }

    // ---------- ต่อบล็อก: เรียงค่า, อันดับ, ตาราง f ----------
    blkSortedPos.assign(nb, {});
    rankIn.assign(n + 2, 0);
    fTab.assign(nb, {});
    for (int b = 0; b < nb; b++) {
        int sz = blkR[b] - blkL[b] + 1;
        vector<int> ps(sz);
        for (int k = 0; k < sz; k++) ps[k] = blkL[b] + k;
        sort(ps.begin(), ps.end(), [&](int x, int y) { return P[x] < P[y]; });
        blkSortedPos[b] = ps;
        for (int k = 0; k < sz; k++) rankIn[ps[k]] = k + 1;

        int W = sz + 1;
        vector<int> f((size_t)W * W, 0);
        // ใส่ 1 ที่ (rank_i, rank_j) ของทุกคู่ที่ i < j และ rank_i < rank_j
        for (int i = blkL[b]; i <= blkR[b]; i++)
            for (int j = i + 1; j <= blkR[b]; j++)
                if (rankIn[i] < rankIn[j]) f[(size_t)rankIn[j] * W + rankIn[i]]++;
        // ผลรวมสะสมสองมิติบน layout f[v][u]
        for (int v = 1; v < W; v++)
            for (int u = 1; u < W; u++)
                f[(size_t)v * W + u] += f[(size_t)(v - 1) * W + u] + f[(size_t)v * W + u - 1]
                                      - f[(size_t)(v - 1) * W + u - 1];
        fTab[b] = move(f);
    }

    // ---------- อ่านคำถาม ----------
    vector<int> qr1(m), qr2(m), qc1(m), qc2(m);
    vector<ll> ans(m, 0);
    for (int k = 0; k < m; k++) { qr1[k] = readInt(); qr2[k] = readInt(); qc1[k] = readInt(); qc2[k] = readInt(); }

    // ---------- หมวด "บล็อกเต็มคนละบล็อก": กวาดค่าจากน้อยไปมาก ----------
    // colTotal[bx] = จำนวนคู่ที่ปลายบนอยู่บล็อก bx และปลายล่างอยู่บล็อกใดก็ได้ที่เล็กกว่า bx
    // E[bx][b1]   = จำนวนคู่ที่ปลายบนอยู่บล็อก bx และปลายล่างอยู่บล็อกที่เล็กกว่า b1
    // ทั้งสองนับเฉพาะของที่ใส่ไปแล้ว (ค่า <= เวลาปัจจุบัน) และ P_i < P_j รับประกันโดยลำดับการใส่
    vector<ll> colTotal(nb, 0);
    vector<ll> E((size_t)nb * nb, 0);
    vector<int> c(nb, 0);
    // เหตุการณ์: คำถาม k ต้องอ่านค่าที่เวลา c2 (บวก) และที่เวลา c1-1 (ลบ)
    vector<vector<pair<int,int>>> evAt(n + 2);   // evAt[t] = (k, sign)
    for (int k = 0; k < m; k++) {
        int b1 = blkOf[qr1[k]], b2 = blkOf[qr2[k]];
        if (b2 - b1 < 2) continue;               // ไม่มีบล็อกเต็มสองบล็อกขึ้นไป
        evAt[qc2[k]].push_back({k, +1});
        if (qc1[k] - 1 >= 1) evAt[qc1[k] - 1].push_back({k, -1});
    }
    for (int t = 1; t <= n; t++) {
        int pos = posOf[t], bx = blkOf[pos];
        // อัปเดตก่อนนับตัวเอง: คู่ใหม่เกิดกับของที่ใส่ไปแล้วเท่านั้น
        ll run = 0, pref = 0;
        ll *Ebase = &E[bx];
        for (int b1 = 0; b1 < nb; b1++) {
            if (b1 == bx) pref = run;      // run ตอนนี้คือผลรวมของบล็อกที่ < bx พอดี ไม่ต้องวนซ้ำ
            Ebase[(size_t)b1 * nb] += run;
            run += c[b1];
        }
        colTotal[bx] += pref;
        c[bx]++;

        for (auto &ev : evAt[t]) {
            int k = ev.first, sg = ev.second;
            int bb1 = blkOf[qr1[k]] + 1, bb2 = blkOf[qr2[k]] - 1;
            ll s = 0;
            const ll *Erow = &E[(size_t)bb1 * nb];   // ติดกันในหน่วยความจำ
            for (int bx2 = bb1; bx2 <= bb2; bx2++) s += colTotal[bx2] - Erow[bx2];
            ans[k] += sg * s;
        }
    }

    // ---------- ประกอบคำตอบของแต่ละคำถาม ----------
    // BIT เล็กสำหรับหมวดเศษ (ดัชนีอัดเป็น 0..cntPart-1)
    vector<int> bitArr;
    auto bitInit = [&](int sz) { bitArr.assign(sz + 1, 0); };
    auto bitAdd  = [&](int i)  { for (++i; i < (int)bitArr.size(); i += i & -i) bitArr[i]++; };
    auto bitSum  = [&](int i)  { int s = 0; for (++i; i > 0; i -= i & -i) s += bitArr[i]; return s; };

    vector<int> partPos;    // ตำแหน่งของชิ้นเศษ เรียงตามค่า
    vector<int> idxOfPos;   // ตำแหน่ง -> ลำดับที่ (ตามตำแหน่ง) ในกองเศษ
    idxOfPos.assign(n + 2, -1);

    for (int k = 0; k < m; k++) {
        int r1 = qr1[k], r2 = qr2[k], c1 = qc1[k], c2 = qc2[k];
        if (c1 > c2 || r1 > r2) { ans[k] = 0; continue; }
        int b1 = blkOf[r1], b2 = blkOf[r2];
        ll res = ans[k];   // ส่วนที่ได้จากการกวาดแล้ว (หมวดบล็อกเต็มคนละบล็อก)

        if (b1 == b2) {
            // ทั้งคำถามอยู่ในบล็อกเดียว: นับตรง ๆ ด้วย BIT บนอันดับภายในบล็อก
            res = 0;
            int sz = blkR[b1] - blkL[b1] + 1;
            bitInit(sz + 1);
            for (int i = r1; i <= r2; i++) {
                int v = P[i];
                if (v < c1 || v > c2) continue;
                res += bitSum(rankIn[i] - 1);
                bitAdd(rankIn[i]);
            }
            ans[k] = res;
            continue;
        }

        int bb1 = b1 + 1, bb2 = b2 - 1;          // ช่วงบล็อกเต็ม (อาจว่าง)
        bool hasFull = bb1 <= bb2;
        int L = hasFull ? blkL[bb1] : 0, R = hasFull ? blkR[bb2] : -1;

        // (ก)+(ข) รอบเดียวเหนือบล็อกเต็ม อ่านตาราง F สี่ครั้งต่อบล็อก
        //   lo_b = จำนวนค่าในบล็อก b ที่ <= c1-1   (ใช้เป็นขอบล่างของอันดับ และเป็นขนาดของ A)
        //   hi_b = จำนวนค่าในบล็อก b ที่ <= c2     (ใช้เป็นขอบบนของอันดับ)
        // (ก) คู่ที่อยู่ในบล็อกเต็มบล็อกเดียวกัน
        // (ข) แก้แถบค่าของหมวดบล็อกเต็มคนละบล็อก: ลบส่วน Cross(A, S) ออก
        //     A = ค่า <= c1-1, S = ค่าใน [c1,c2]; ค่าใน A น้อยกว่าใน S ทุกตัว ปลายล่างจึงเป็นฝั่ง A เสมอ
        if (hasFull) {
            int lowCap = c1 - 1;
            const int *rowLo = lowCap >= 1 ? &F[(size_t)lowCap * NBP1] : nullptr;
            const int *rowHi = &F[(size_t)c2 * NBP1];
            ll runA = 0, cross = 0;
            for (int b = bb1; b <= bb2; b++) {
                int lo = rowLo ? rowLo[b + 1] - rowLo[b] : 0;
                int hi = rowHi[b + 1] - rowHi[b];
                res += withinBlockRank(b, lo + 1, hi);
                if (lowCap >= 1) { cross += (ll)(hi - lo) * runA; runA += lo; }
            }
            res -= cross;
        }

        // รวบรวมชิ้นเศษสองฝั่ง โดยดึงออกมาเรียงตามค่าอยู่แล้ว (ไม่ต้อง sort)
        partPos.clear();
        {
            // ซ้ายเศษ = ตำแหน่ง r1..blkR[b1] ; ขวาเศษ = blkL[b2]..r2
            const vector<int> &sl = blkSortedPos[b1];
            const vector<int> &sr = blkSortedPos[b2];
            size_t a = 0, b = 0;
            while (a < sl.size() || b < sr.size()) {
                while (a < sl.size() && (sl[a] < r1 || P[sl[a]] < c1 || P[sl[a]] > c2)) a++;
                while (b < sr.size() && (sr[b] > r2 || P[sr[b]] < c1 || P[sr[b]] > c2)) b++;
                if (a >= sl.size() && b >= sr.size()) break;
                if (b >= sr.size() || (a < sl.size() && P[sl[a]] < P[sr[b]])) partPos.push_back(sl[a++]);
                else partPos.push_back(sr[b++]);
            }
        }
        int cntPart = (int)partPos.size();
        // ลำดับตามตำแหน่ง: ซ้ายเศษมาก่อนขวาเศษเสมอ จึงจัดลำดับด้วยตำแหน่งจริงได้เลย
        {
            vector<int> byPos = partPos;
            sort(byPos.begin(), byPos.end());
            for (int t = 0; t < cntPart; t++) idxOfPos[byPos[t]] = t;
        }
        // (ค) คู่ที่ปลายทั้งสองเป็นชิ้นเศษ (ซ้ายxซ้าย, ขวาxขวา, ซ้ายxขวา) รวบเป็นรอบเดียว
        bitInit(cntPart + 1);
        for (int t = 0; t < cntPart; t++) {
            int id = idxOfPos[partPos[t]];
            res += bitSum(id - 1);      // ของที่ค่าน้อยกว่า และตำแหน่งอยู่ก่อนหน้า
            bitAdd(id);
        }
        // (ง) ชิ้นเศษ x บล็อกเต็ม
        if (hasFull) {
            for (int pos : partPos) {
                int v = P[pos];
                if (pos <= blkR[b1]) res += cntBlocks(bb1, bb2, v + 1, c2);   // เศษซ้ายเป็นปลายล่าง
                else                 res += cntBlocks(bb1, bb2, c1, v - 1);   // เศษขวาเป็นปลายบน
            }
        }
        for (int pos : partPos) idxOfPos[pos] = -1;
        ans[k] = res;
        (void)L; (void)R;
    }

    for (int k = 0; k < m; k++) printf("%lld\n", ans[k]);
    return 0;
}

ดูโค้ดของ subtask ขนาดเล็ก

tears_small.cpp

// NOI 2020 "Tears" (2043) - เฉลย subtask: N, M <= 5000
// เดินหน้าต่างตามลำดับดัชนี แล้วนับด้วย BIT บนแกนค่า  O(ความยาวช่วง * log n) ต่อคำถาม
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, m;
vector<int> P, t;

void add(int i, int v) { for (; i <= n; i += i & -i) t[i] += v; }
int sum(int i) { int s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; }

int main() {
    if (scanf("%d %d", &n, &m) != 2) return 0;
    P.assign(n + 1, 0); t.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) if (scanf("%d", &P[i]) != 1) return 0;
    vector<int> touched;
    touched.reserve(n);
    for (int k = 0; k < m; k++) {
        int r1, r2, c1, c2;
        if (scanf("%d %d %d %d", &r1, &r2, &c1, &c2) != 4) return 0;
        ll s = 0;
        touched.clear();
        if (r1 <= r2 && c1 <= c2) {
            int base = sum(c1 - 1);            // ค่าที่ต่ำกว่าแถบ ไม่มีวันถูกใส่ จึงคงที่
            (void)base;
            for (int i = r1; i <= r2; i++) {
                int v = P[i];
                if (v < c1 || v > c2) continue;
                s += sum(v - 1) - sum(c1 - 1);  // ของที่ใส่แล้วและค่าน้อยกว่า v (อยู่ในแถบแน่นอน)
                add(v, 1);
                touched.push_back(v);
            }
            for (int v : touched) add(v, -1);
        }
        printf("%lld\n", s);
    }
    return 0;
}

ดูตัวตรวจที่ใช้ stress test

brute_tears.cpp

// NOI 2020 "Tears" (2043) - ตัวตรวจ อ่านจากนิยามโจทย์ตรง ๆ  O(N^2) ต่อคำถาม
// ใช้ได้กับ subtask N, M <= 10 และเป็นตัวเทียบในการ stress test
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int n, m;
    if (scanf("%d %d", &n, &m) != 2) return 0;
    vector<int> P(n + 1);
    for (int i = 1; i <= n; i++) if (scanf("%d", &P[i]) != 1) return 0;
    for (int k = 0; k < m; k++) {
        int r1, r2, c1, c2;
        if (scanf("%d %d %d %d", &r1, &r2, &c1, &c2) != 4) return 0;
        ll s = 0;
        for (int i = 1; i <= n; i++) {
            if (i < r1 || i > r2 || P[i] < c1 || P[i] > c2) continue;
            for (int j = i + 1; j <= n; j++) {
                if (j < r1 || j > r2 || P[j] < c1 || P[j] > c2) continue;
                if (P[i] < P[j]) s++;      // คู่ที่เพิ่มขึ้น ตามที่โจทย์นิยาม
            }
        }
        printf("%lld\n", s);
    }
    return 0;
}

ผ่านตัวอย่างของโจทย์ รวมถึงรายการคู่ที่โจทย์ไล่ให้ในยุคที่ 1 และ 2
สุ่มอีก 980 เคส N = 8, 20, 45, 120, 400, 1200, 4000 ลำดับสี่แบบ (สุ่ม, กลับหลัง, เรียงแล้ว, ครึ่งเรียง)
เทียบกับโค้ด subtask ทุกเคส และกับตัวตรวจเมื่อ N ไม่เกิน 120 ผิด 0 เคส

เวลาและหน่วยความจำที่วัดจริง ที่ N = 100,000, M = 200,000
รูปแบบคำถาม	วินาที	เมกะไบต์
กรอบสุ่มทั้งสองแกน	3.66	365
กรอบเต็มระนาบทุกคำถาม	1.7	359
กรอบยาวเกือบเต็มแกนดัชนี	3.59	363
กรอบสั้น	0.77	363

วัดบน WSL Ubuntu, g++ 11.4.0, คอมไพล์ด้วย -O2 แย่สุด 3.66 วินาที จากลิมิต 4 วินาที คือใช้งบเวลาไป 92 เปอร์เซ็นต์ ซึ่งถือว่าเฉียด ส่วนหน่วยความจำแย่สุด 365 เมกะไบต์ จากลิมิต 1024 ยังเหลือเยอะ

คำว่าตรวจแล้วในหน้านี้หมายถึงตรวจกับตัวตรวจของเราเองและตัวอย่างในโจทย์ ยังไม่ได้ส่งเข้าเครื่องตรวจของ programming.in.th และเวลาที่วัดเป็นของเครื่องที่ใช้เขียน ไม่ใช่ของเครื่องตรวจ ตัวเลข 92 เปอร์เซ็นต์จึงเป็นตัวเลขที่ควรระวัง

เช็กความเข้าใจ

สามข้อนี้ตอบได้จากสิ่งที่อ่านมา ลองคิดก่อนแล้วค่อยเปิดคำตอบ

ข้อ 1. ถ้าโจทย์เปลี่ยนเป็นนับคู่ที่ค่าลดลง (i มาก่อน j แต่ค่าของ i มากกว่า) ต้องแก้โค้ดตรงไหนบ้าง

ดูคำตอบข้อ 1

ไม่ต้องแก้อัลกอริทึมเลย กลับค่าก่อนเข้าโปรแกรม ให้ค่า P_i กลายเป็น N + 1 − P_i คู่ที่ค่าลดลงจะกลายเป็นคู่ที่ค่าเพิ่มขึ้น แล้วแถบค่า [c1, c2] ก็กลับเป็น [N + 1 − c2, N + 1 − c1] ตามกัน

ข้อ 2. ตาราง E เก็บแค่ "ปลายล่างอยู่ก่อนบล็อก b1" ทำไมไม่ต้องมีอีกตารางสำหรับ "ปลายบนอยู่หลังบล็อก b2"

ดูคำตอบข้อ 2

เพราะผลรวมไล่ bx ตั้งแต่ b1 ถึง b2 เท่านั้น bx คือบล็อกของปลายบน การเลือกช่วงของผลรวมจึงกันปลายบนที่อยู่หลัง b2 ออกไปเองแล้ว ปลายล่างเป็นด้านเดียวที่ต้องหักออกด้วย E

ข้อ 3. ถ้าเลือก B = N (บล็อกเดียว) หรือ B = 1 (ตัวละบล็อก) จะเกิดอะไรขึ้น

ดูคำตอบข้อ 3

B = N ทุกอย่างกลายเป็นเศษ คำถามหนึ่งข้อต้องไล่ทั้งช่วงด้วย BIT เท่ากับย้อนกลับไปวิธีที่ 2 ซึ่งช้าเกินไป

B = 1 ไม่มีเศษเลย แต่ตาราง E มีขนาดจำนวนบล็อกยกกำลังสอง คือ N² = 10,000,000,000 ช่อง ใหญ่เกินหน่วยความจำ ขนาดราว √N จึงอยู่ตรงกลางพอดี เศษไม่ยาวเกิน ตารางไม่ใหญ่เกิน (ตอนที่ 3 เล่าว่าทำไมโค้ดจริงเลือกเล็กกว่า √N นิดหนึ่ง)

ท่าที่ติดมือกลับไป

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

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

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

สรุปบรรทัดเดียว

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

แหล่งที่มา

โจทย์ต้นทาง programming.in.th ข้อ 2043 (โศกนาฏกรรม) ที่มาคือ The 37th CCF National Olympiad in Informatics (NOI 2020)
หน้าโจทย์เดียวกันบนหลัวกู่ รหัส P6774 luogu.com.cn/problem/P6774
บทวิเคราะห์ภาษาจีนที่ใช้เทียบแนวทางการหั่นบล็อก luogu.com.cn/article/ho83bfoe และ luogu.com.cn/article/4939268d (คำอธิบายในหน้านี้เขียนใหม่ด้วยคำของผมเอง และการอ่านโจทย์พิสูจน์จากตัวอย่างของโจทย์เอง ไม่ได้เชื่อบทวิเคราะห์ ซึ่งบทสรุปที่ดึงมาครั้งแรกอ่านเงื่อนไขคู่กลับด้าน)

v	b = 1	b = 2	b = 3	b = 4
0	0	0	0	0
1	1	1	1	1
2	1	2	2	2
3	1	2	3	3
4	1	2	3	4
5	1	3	4	5
6	1	3	5	6
7	2	4	6	7
8	2	4	6	8
9	2	5	7	9
10	2	5	8	10
11	3	6	9	11
12	3	6	9	12

v	b = 1	b = 2	b = 3	b = 4
0	0	0	0	0
1	1	1	1	1
2	1	2	2	2
3	1	2	3	3
4	1	2	3	4
5	1	3	4	5
6	1	3	5	6
7	2	4	6	7
8	2	4	6	8
9	2	5	7	9
10	2	5	8	10
11	3	6	9	11
12	3	6	9	12

v	b = 1	b = 2	b = 3	b = 4
0	0	0	0	0
1	1	1	1	1
2	1	2	2	2
3	1	2	3	3
4	1	2	3	4
5	1	3	4	5
6	1	3	5	6
7	2	4	6	7
8	2	4	6	8
9	2	5	7	9
10	2	5	8	10
11	3	6	9	11
12	3	6	9	12