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

• ตอบค่าที่ช่อง ๆ หนึ่ง (point query)
• หาผลรวมของช่วง ๆ หนึ่ง (range query)
• เปลี่ยนค่าที่ช่อง ๆ หนึ่ง (point update)
• เปลี่ยนค่าช่วง ๆ หนึ่งให้กลายเป็น 0 (range update)

โครงสร้างข้อมูลชนิดหนึ่งที่สามารถทำงานเหล่านี้ได้เร็ว ๆ คือ segment tree with lazy propagation ซึ่งสามารถทำงานแต่ละอย่างในนี้ได้ใน $\mathcal{O}(\log N)$

ในการดึงเชือกแต่ละครั้ง ให้ point update ที่ช่อง ๆ นั้นเพิ่มด้วยความยาวเชือกที่ดึง จากนั้นให้หาว่าเชือกจะถูกดึงไปถึงช่วงที่เท่าไหร่ในทางซ้ายด้วยการ binary search แล้วเปลี่ยนช่วงเหล่านั้นให้กลายเป็น 0 และทำเช่นนี้สำหรับทางขวาด้วย อัลกอริธึมนี้สามารถแก้โจทย์ได้ใน $\mathcal{O}(N+M\log^2N)$

อัลกอริธึมนี้สามารถพัฒนาให้ดีขึ้นได้ โดยแทนที่เราจะ binary search ให้เราเลือก traverse ลงไปใน segment tree เพื่อหาว่าเชือกจะดึงไปถึงช่องที่เท่าไหร่ time complexity ของอัลกอริธึมเราจึงเป็น $\mathcal{O}(N+M\log N)$

Alternative Solution

สังเกตว่าการดึงเชือกของเราจะทำให้อาเรย์เต็มไปด้วยเลข 0 จึงนำไปสู่ไอเดียในการ "ยุบ" 0 ที่ติดกันให้หายไป โดยสามารถทำได้โดยการเก็บและอัพเดทค่า nextNonZero[i] และ prevNonZero[i] ตลอดการทำงาน เพื่อที่ในขณะที่เราไล่ดึงเชือกเราจะสามารถข้ามลำดับของ 0 ที่ติดกันยาว ๆ เพื่อลดเวลาการทำงาน

optimization นี้อาจจะดูเล็ก ๆ แต่ก็เพียงพอแล้วที่จะทำให้อัลกอริธึมของเราทำงานในเวลาที่กำหนด เพราะจริง ๆ แล้วอัลกอริธึมของเรานั้นทำงานในเวลา amortized $\mathcal{O}(M+N)$ นั่นเอง

ในการพิสูจน์ เราจะใช้ potential method ในการวิเคราะห์เวลาการทำงาน โดยเราจะให้ $\Phi(S)$ มีค่าเท่ากับของตัวเลขในอาเรย์ปัจจุบันของเรา โดยจะไม่นับ 0 ที่อยู่ในอาร์เรย์ เนื่องจากเราสามารถข้าม 0 ได้โดยใช้วิธีที่กล่าวไว้ข้างต้น ทำให้เราสามารถมองอาร์เรย์ว่ามันไม่มี 0 อยู่ในนั้นเลย

ในตอนเริ่มต้น เราจะให้อาร์เรย์ของเราไม่มีตัวเลขอะไรอยู่ในนั้นเลย ดังนั้น $\Phi(S_0) = 0$ และเนื่องจากจำนวนตัวเลขในอาร์เรย์จะไม่มีทางติดลบ ดังนั้น $\Phi(S_i) \geq 0$ เสมอ

จากนั้นเราจะนิยาม operation ที่เราต้องใช้ 2 อย่าง

• init ทำการสร้างอาร์เรย์ตอนเริ่มของเรา จะทำงานแค่ตอนเริ่มแค่ครั้งเดียว
• update ทำการดึงเชือกและอัพเดทค่าต่าง ๆ จะทำงานทั้งหมด

ในส่วนต่อไปจะเป็นการวิเคราะห์เวลาในแต่ละอัน

init

actual cost $c$ มีค่าเท่ากับ $N$ เมื่อ $N$ คือจำนวนข้อมูลนำเข้า ทำให้ potential เพิ่มขึ้นจาก 0 ไปเป็น $N$ ดังนั้น amortized cost $c'$ จะมีค่าเท่ากับ

$c' = c + \Phi(S')-\Phi(S) = N + (N-0) = 2N$

update

สมมติว่าในการดึงเชือกมีการเปลี่ยนแปลงข้อมูลของตัวเลขที่อยู่ในอาร์เรย์ด้านซ้าย $L$ ตัว และด้านขวา $R$ ตัว จะได้ว่า จะมี 0 ที่เพิ่มขึ้นอย่างน้อย $(L-1) + (R-1)-1$ ตัว (เทอม -1 เกิดขึ้นจากกรณีที่เราดึงเชือกที่ส่วนที่มีความตึงเป็น 0 จึงทำให้ 0 จะลดลง 1 ตัว)

ดังนั้นเราถ้าเราให้ $\Phi(S) = n$ จะได้ว่า $\Phi(S') \leq n-((L-1)+(R-1)-1) = n-L-R+3$ นั่นคือ $\Phi(S')-\Phi(S) \leq -L-R+3$

เนื่องจาก actual cost $c$ มีค่าเท่ากับ $L+R$ amortized cost $c'$ จะมีค่าเท่ากับ

$c' = c + \Phi(S')-\Phi(S) \leq L+R + (-L-R+3) = 3$

ดังนั้นจะได้ว่า init ทำงานใน $\mathcal{O}(N)$ และ update ทำงานใน amortized $\mathcal{O}(1)$ นั่นเอง

ดังนั้นอัลกอริธึมของเราจะทำงานในเวลา amortized $\mathcal{O}(N+M)$