programming.in.th · ข้อ 2043

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

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

★★★★★ offlineprefix sumBITcounting อ่าน 9 นาที 12 กันยายน 2026

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

L ได้รับคำถามจากคนฉลาด ๆ ว่าถ้าปริภูมิเวลาเขียนลงระนาบสองมิติได้ เหตุการณ์หนึ่งก็เป็นจุดหนึ่งจุด และยุคสมัยหนึ่งก็เป็นสี่เหลี่ยมผืนผ้าหนึ่งรูป

เหตุการณ์มี 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 และถ้าเผลออ่านลำดับตัวเลขในกรอบเป็นดัชนีสลับกับค่า ยุคที่ 1 จะได้ 0 ทั้งคู่ไม่ใช่ 1

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

ใบ้

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

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

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

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

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

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

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

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

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

ผมไม่ได้เริ่มจากการนึกท่าออก ผมเริ่มจากการนับว่าเรามีงบเท่าไร คำถาม 200,000 ข้อ ถ้าข้อหนึ่งยอมให้ใช้เวลาเท่ากับรากที่สองของ 100,000 คือราว 316 ก้าว รวมแล้วราว 63 ล้านก้าว ซึ่งพอดีกับ 4 วินาที แปลว่าเป้าหมายคือหาวิธีตอบข้อละรากที่สองของ N ให้ได้ ไม่ใช่ข้อละ log

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

คู่ที่เรานับมี i มาก่อน j อยู่แล้ว ดังนั้นถ้า i อยู่ในช่วง [r1, r2] และ j ก็อยู่ในช่วงเดียวกัน เงื่อนไข j ≥ r1 เป็นจริงฟรี ๆ เพราะ j มากกว่า i อยู่แล้ว และ i ≤ r2 ก็เป็นจริงฟรีเช่นกัน เหลือของจริงแค่สองข้อ เรื่องค่าก็เหมือนกันเป๊ะ เพราะคู่ที่นับมีค่าของ i น้อยกว่าค่าของ j อยู่แล้ว

สี่เงื่อนไข ปลายละข้อ

ดัชนีอยู่ในกรอบทั้งคู่ ยุบเหลือ i ≥ r1 กับ j ≤ r2
ค่าอยู่ในกรอบทั้งคู่ ยุบเหลือ P_i ≥ c1 กับ P_j ≤ c2

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

เฉลย ตอนที่ 2 · หั่นเป็นบล็อก แล้วแตกเป็นหกหมวด

หั่นแกนดัชนีเป็นบล็อกละ B ตำแหน่ง ช่วง [r1, r2] ของคำถามหนึ่งจะแตกเป็นสามท่อนคือ เศษซ้าย บล็อกเต็มตรงกลาง และเศษขวา เศษสองฝั่งยาวไม่เกิน B ตำแหน่ง ส่วนตรงกลางเป็นบล็อกเต็มทั้งก้อน คู่หนึ่งคู่มีปลายสองข้าง จึงตกอยู่ในหกหมวด

หกหมวดของคู่ กับวิธีจัดการแต่ละหมวด
ปลายล่างอยู่	ปลายบนอยู่	จัดการยังไง
เศษซ้าย	เศษซ้าย	รวบสามหมวดนี้เป็นรอบเดียว ดึงชิ้นเศษออกมาแบบเรียงตามค่าอยู่แล้ว แล้วนับด้วย BIT
เศษขวา	เศษขวา	รวมอยู่ในรอบเดียวกันข้างบน
เศษซ้าย	เศษขวา	รวมอยู่ในรอบเดียวกันข้างบน
เศษซ้าย	บล็อกเต็ม	ต่อชิ้นเศษหนึ่งชิ้น ถามตารางพรีฟิกซ์ครั้งเดียวจบ
บล็อกเต็ม	เศษขวา	เหมือนบรรทัดบน แค่สลับข้าง
บล็อกเต็ม	บล็อกเต็ม	แยกเป็นบล็อกเดียวกันกับคนละบล็อก อันหลังคือตอนที่ 3

เศษสองฝั่งยาวรวมไม่เกิน 278 ตำแหน่งที่ขอบเขตเต็ม ส่วนบล็อกเต็มมีไม่เกิน 720 บล็อก ทั้งสองจำนวนอยู่ในระดับรากที่สองของ N ซึ่งตรงกับงบที่ตั้งไว้

หมวดที่ปลายข้างหนึ่งเป็นชิ้นเศษและอีกข้างอยู่ในบล็อกเต็ม ตอบได้ทันทีถ้ามีตาราง F[ค่า][บล็อก] ที่บอกว่าบล็อก 0 ถึงบล็อกนั้นมีกี่ตำแหน่งที่ค่าไม่เกินค่าที่ระบุ เพราะช่วงบล็อกเต็มมีขอบตรงกับขอบบล็อกพอดี การนับจึงเป็นการลบกันสองครั้ง

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

เฉลย ตอนที่ 3 · หมวดที่ยากที่สุด กวาดค่าแล้วเก็บคู่ข้ามบล็อก

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

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

colTotal[bx] คือจำนวนคู่ที่ปลายบนอยู่บล็อก bx และปลายล่างอยู่บล็อกใดก็ได้ที่เล็กกว่า
E[b1][bx] คือจำนวนคู่ที่ปลายบนอยู่บล็อก bx และปลายล่างอยู่บล็อกที่เล็กกว่า b1

คำถามที่ช่วงบล็อกเต็มเป็น b1 ถึง b2 จึงตอบด้วยการบวก colTotal[bx] − E[b1][bx] ไล่ตั้งแต่ bx = b1 ถึง b2 ซึ่งเป็นการอ่านแถวเดียวของ E ติดกันรวดเดียว

เหลือเรื่องเดียวคือขอบค่าล่าง เพราะการกวาดให้ผลของ "ค่าไม่เกิน c2" ไม่ใช่ "ค่าอยู่ระหว่าง c1 ถึง c2" ตรงนี้ใช้เอกลักษณ์ที่ตรงไปตรงมา ถ้า A คือของที่ค่าไม่เกิน c1 − 1 และ S คือของที่ค่าอยู่ใน [c1, c2]

สูตรที่ยุบขอบค่าสองด้านให้เหลือพรีฟิกซ์

คู่ที่อยู่ใน S ทั้งคู่ = (คู่ที่ค่าไม่เกิน c2 ทั้งคู่) − (คู่ที่ค่าไม่เกิน c1 − 1 ทั้งคู่) − Cross(A, S)

สองพจน์แรกคืออ่านค่าจากการกวาดที่เวลา c2 และที่เวลา c1 − 1 ส่วน Cross(A, S) คิดง่ายกว่าที่คิด เพราะค่าทุกตัวใน A น้อยกว่าค่าทุกตัวใน S ดังนั้นในคู่ข้าม ปลายล่างต้องเป็นฝั่ง A เสมอ ไม่มีทางสลับ Cross จึงเป็นแค่ผลรวมของจำนวนสมาชิก A ในบล็อกก่อนหน้า คูณจำนวนสมาชิก S ในบล็อกปัจจุบัน ไล่ทีละบล็อก ซึ่งอ่านจากตาราง F ได้ทั้งหมด

เฉลย ตอนที่ 4 · จาก 14.75 วินาที เหลือ 3.66 โดยไม่แตะอัลกอริทึม

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

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

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

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

เร็วขึ้น 4 เท่า โดยที่จำนวนคำสั่งที่รันแทบไม่เปลี่ยน

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

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

โค้ด

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

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 ผิดศูนย์เคส

เวลาและหน่วยความจำที่วัดจริง ที่ 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 เปอร์เซ็นต์จึงเป็นตัวเลขที่ควรระวัง

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

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

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

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

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

แหล่งที่มา

โจทย์ต้นทาง 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 (คำอธิบายในหน้านี้เขียนใหม่ด้วยคำของผมเอง และการอ่านโจทย์พิสูจน์จากตัวอย่างของโจทย์เอง ไม่ได้เชื่อบทวิเคราะห์ ซึ่งบทสรุปที่ดึงมาครั้งแรกอ่านเงื่อนไขคู่กลับด้าน)