ข้อนี้ต้องการหาว่าสำหรับอาเรย์ $A[1..N]$ ที่มีค่าตั้งแต่ $1$ ถึง $N$ แบบไม่ซ้ำกัน จะมีกี่คู่ $(l,r)$ ที่ $A[l..r]$ มีค่ามัธยฐานเท่ากับ $k$

เคส $N \leq 1000$

จากนิยามของมัธยฐานจะสังเกตได้ว่า $k$ จะต้องอยู่ใน $A[l..r]$ และใน $A[l..r]$ จะมีจำนวนค่าที่มากกว่า $k$ เท่ากับจำนวนค่าที่น้อยกว่า $k$

กำหนดให้ $x$ เป็นดัชนีที่ทำให้ $A[x]=k$ และนิยาม $C[i] = (A[i] > k) - (A[i] < k)$ กล่าวคือ $C[i]$ เป็น $1$ เมื่อ $A[i] >k$ และ $-1$ เมื่อ $A[i] <k$

โจทย์จะกลายเป็นการหาจำนวนคู่ $(l,r)$ ที่ทำให้ $\Sigma_{i=l}^{x} C[i] + \Sigma_{i=x}^r C[i]= 0$ ซึ่งหมายความว่าใน $A[l..r]$ มีจำนวนที่มากกว่า $k$ และน้อยกว่า $k$ เท่ากัน

นิยาม $SL[l]=\Sigma_{i=l}^{x} C[i]$ และ $SR[r]=\Sigma_{i=x}^r C[i]$ จะได้ว่า $-N \leq SL[l] \leq N$ และ $-N \leq SR[l] \leq N$ เพราะมีได้อย่างมาก $N$ ตัวที่มากกว่าหรือน้อยกว่า $k$

สำหรับเคส $n \leq 1000$ สามารถไล่ทุกคู่ $(l,r)$ ที่ $l \leq x \leq r$ ได้โดยตรงและตรวจสอบว่า $SL[l] + SR[r] =0$ หรือไม่สำหรับแต่ละคู่

การคำนวณค่า $C[1..N]$ $SL[1..x]$ และ $SR[x..N]$ ใช้เวลา $\mathcal{O}(N)$ การเช็คแต่ละคู่ $(l,r)$ ใช้เวลา $\mathcal{O}(N^2)$

เคส $N \leq 1000000$

เมื่อกำหนัด $L_s$ เป็นจำนวน $l$ ที่ทำให้ $SL[l]=s$ และ $R_s$ เป็นจำนวน $r$ ที่ทำให้ $SR[r] =s$ จะได้ว่าคำตอบคือ $\sum_{s=-N}^N L_sR_{-s}$ (เพราะเมื่อ $SL[l] =s$ และ $SR[r] =-s$ จะได้ว่า $\Sigma_{i=l}^{x} C[i] + \Sigma_{i=x}^r C[i]= s - s = 0$)

เราสามารถคำนวณ $L_s$ ได้โดยการไล่คำนวณ $SL[l]$ ตั้งแต่ $l=x$ ไปจนถึง $l=1$ และเพิ่ม $L_s$ ทุกครั้งที่ $SL[l] = s$ โดยเริ่มจาก $SL[x] = 0$ และคำนวณ $SL[l] = SL[l+1] + C[l]$ สำหรับ $l$ ต่อๆ ไป สามารถใช้วิธีในทำนองเดียวกันในการคำนวณ $R_s$ โดยคำนวณ $SR[r]$ เริ่มจาก $r=x$ ไปจนถึง $r=N$

Time Complexity: การคำนวณ $SL[1..x]$ และ $SR[x..N]$ เพื่อคำนวณ $L_s$ และ $R_s$ ใช้เวลารวมกัน $\mathcal{O}(N)$ และการคำนวณ $\sum_{s=-N}^N L_sR_{-s}$ ใช้เวลา $\mathcal{O}(N)$ ทั้งหมดจึงใช้เวลา $\mathcal{O}(N)$