บ่อยครั้งที่เจอโจทย์ที่แต่ละคำถาม (query) เป็นอิสระต่อกัน เราสามารถนำ query มาเรียงจากน้อยไปมากหรือมากไปน้อยเพื่อให้การคำนวณสะดวกมากขึ้นแล้วค่อยเรียงกลับเป็นแบบเดิมตอนแสดงผล เทคนิคนี้เรียกว่า offline query

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

ยกตัวอย่าง หากความสูงของพื้นเป็น 1, 5, 4, 6, 12, 13, 7, 8, 3 (เลขที่เน้นหนาคือพื้นที่ถูกทุบไปแล้ว และเปรียบเสมือนว่าไม่มีอยู่จริง)

• หากมีพลังอย่างน้อย 6 หน่วย ความสูงของพื้นเป็น 1, 5, 4, 6, 12, 13, 7, 8, 3
• หากมีพลังน้อยกว่า 6 หน่วย ความสูงของพื้นเป็น 1, 5, 4, 6, 6, 6, 7, 8, 3
• หากมีพลังน้อยกว่า 4 หน่วย ความสูงของพื้นเป็น 1, 4, 4, 6, 6, 6, 7, 8, 3
• หากมีพลังน้อยกว่า 3 หน่วย ความสูงของพื้นเป็น 1, 1, 1, 1, 1, 1, 1, 1, 3
• หากมีพลังน้อยกว่า 2 หน่วย ความสูงของพื้นเป็น 1, 1, 1, 1, 1, 1, 1, 1, 1

เราสามารถใช้ linked list เพื่อเก็บลำดับความสูงของพื้นได้โดยตัดพื้นที่ถูกทุบแล้วออกไป นอกจากนี้ ใช้ binary search tree เพื่อเก็บ multiset ของความต่างระหว่างความสูงทุกสองช่องที่อยู่ติดกัน โดยเก็บเป็นคู่อันดับ ตัวหน้า (ตัวที่ใช้เรียง) คือความต่างของความสูง ส่วนตัวหลังคือ address เพื่อให้อ้างอิงถึงตำแหน่งใน linked list ได้

เราจะลดพลังไปเรื่อย ๆ ตาม multiset ที่เก็บไว้ ทำให้เราทราบได้อย่างรวดเร็วว่าพื้นตำแหน่งใดจะถูกทุบ (อ้างอิงได้จากตัวหลังของคู่อันดับที่เก็บ address ไปยัง linked list ไว้) โดยเมื่อทำการทุบ ให้ลบ/เพิ่มสมาชิกใน multiset และ linked list ให้สัมพันธ์กับสถานะของฉาก พร้อมจดขนาดของ linked list ไว้ตอบเมื่อคำนวณถึงระดับพลังที่ตรงกับ query

หากมีความสูงเป็น 1, 5, 4, 6, 12, 13, 7, 8, 3 ตามตัวอย่างก่อนหน้า (ตัวที่เน้นหนาคือค่าใน linked list/multiset ที่ถูกลบ/เปลี่ยนไป)

• ในตอนแรก พลัง $\infty$ หน่วย Linked List ประกอบด้วย 1, 5, 4, 6, 12, 13, 7, 8, 3 และ Multiset ประกอบด้วย 4, -1, 2, 6, 1, -6, 1, -5 (เก็บเรียงจากมากไปน้อย)
• ตัวที่มากที่สุดใน Multiset คือ 6 (ตำแหน่งพื้นความสูง 6 ขึ้นไปความสูง 12) ดังนั้น เมื่อลดพลังเหลือน้อยกว่า 6 จะทำให้ฉาก (Linked List) ประกอบด้วย 1, 5, 4, 6, ... 7, 8, 3 และ Multiset ประกอบด้วย 4, -1, 2, ... 1, 1, -5
• ตัวที่มากที่สุดใน Multiset คือ 4 (ตำแหน่งพื้นความสูง 1 ขึ้นไปความสูง 5) ดังนั้น เมื่อลดพลังเหลือน้อยกว่า 4 จะทำให้ฉาก (Linked List) ประกอบด้วย 1, ..., 4, 6, 7, 8, 3 และ Multiset ประกอบด้วย ... 3, 2, 1, 1, -5
• ตัวที่มากที่สุดใน Multiset คือ 3 (ตำแหน่งพื้นความสูง 1 ขึ้นไปความสูง 4) ดังนั้น เมื่อลดพลังเหลือน้อยกว่า 3 จะทำให้ฉาก (Linked List) ประกอบด้วย 1, ... 3 และ Multiset ประกอบด้วย ... 2
• ตัวที่มากที่สุดใน Multiset คือ 2 (ตำแหน่งพื้นความสูง 1 ขึ้นไปความสูง 3) ดังนั้น เมื่อลดพลังเหลือน้อยกว่า 2 จะทำให้ฉาก (Linked List) ประกอบด้วย 1, ... และ Multiset ประกอบด้วย ... (ว่าง)

อนึ่ง การ implement ขั้นตอนวิธีนี้ อาจเลือกใช้ Union-find Disjoint Set แทน Linked List ได้ โดย

• ทุกครั้งที่ต้องการทุบตำแหน่งที่ $i$ ออก ให้กำหนดให้ parent ของ $i$ เป็น $i-1$
• หากต้องการเข้าถึงที่อยู่ใกล้ $i$ ที่สุดทางด้านซ้ายที่ยังไม่ถูกทุบ สามารถใช้ path compression หา root ใน disjoint set ได้อย่างรวดเร็ว

Time Complexity รวมคือ $O(N \log N + M \log M)$