วิธีการต่อไปนี้ จะนับคำตอบเฉพาะ Palindrome ที่มีความยาวเป็นจำนวนเต็มคี่เท่านั้น สำหรับความยาวที่เป็นจำนวนเต็มคู่ จะใช้วิธีการคล้ายกัน

กำหนดให้ $a_i$ คือตัวอักษรตัวที่ $i$ ของสายอักขระที่โจทย์ให้มา และ $p_i$ คือจำนวนเต็มที่มากที่สุดที่ $a_{i - p_i - 1} \, a_{i - p_i} \, \dots \, a_{i + p_i - 2} \, a_{i + p_i - 1}$ เป็น Palindrome กล่าวคือ $p_i$ เท่ากับความยาวครึ่งหนึ่งของ Palindrome ที่ยาวที่สุดที่มีจุดศูนย์กลางเป็น $i$ นั่นเอง

แต่ละคำถามของโจทย์ เราจะได้ว่าคำตอบคือ $\sum \limits_{l \leq i \leq r} \min(p_i, i - l + 1, r - i + 1)$ เนื่องจากจำนวน Palindrome ที่มีจุดศูนย์กลางเป็น $i$ คือ $p_i$ แต่เราจะนับเฉพาะ Palindrome ที่ไม่เลยช่วง $[l, r]$

กำหนดให้ $mid = \lfloor \frac{l + r}{2} \rfloor$ สังเกตว่าค่าของ $i - l + 1$ จะน้อยกว่า $r - i + 1$ เมื่อ $i \leq mid$ และจะมากกว่าเมื่อ $i > mid$ ทำให้เราจำเป็นต้องเทียบ $p_i$ กับค่าใดค่าหนึ่งเท่านั้น ดังนั้น เราจึงสามารถจัดรูปคำตอบของคำถามเป็น $[\sum \limits_{l \leq i \leq mid} min(p_i, i - l + 1)] + [\sum \limits_{mid < i \leq r} min(p_i, r - i + 1)]$

สำหรับผลรวมด้านซ้าย เราจะสามารถจัดรูปเป็น $\sum \limits_{l \leq i \leq mid} [min(p_i - i, 1 - l) + i]$ หรือ $[\sum \limits_{l \leq i \leq mid} min(p_i - i, 1 - l)] + \frac{(l + mid)(mid - l + 1)}{2}$ ได้

ในทำนองเดียวกัน ผลรวมด้านขวาก็สามารถจัดรูปเป็น $\sum \limits_{mid < i \leq r} [min(p_i + i, 1 + r) - i]$ หรือ $[\sum \limits_{mid < i \leq r} min(p_i + i, 1 + r)] - \frac{(mid + 1 + r)(r - mid)}{2}$ ได้

ดังนั้น ในแต่ละคำถาม เราจำเป็นต้องทราบค่าของ $\sum \limits_{l \leq i \leq mid} min(p_i - i, 1 - l)$ และ $\sum \limits_{mid < i \leq r} min(p_i + i, 1 + r)$ ซึ่งสามารถหาค่าได้ด้วยการใช้ Persistent Segment Tree ภายในเวลา $\mathcal{O}(\log n)$

วิธีการต่อไปนี้ เป็นการหาค่าของ $\sum \limits_{l \leq i \leq mid} min(p_i - i, 1 - l)$ ส่วน $\sum \limits_{mid < i \leq r} min(p_i + i, 1 + r)$ จะใช้วิธีที่คล้ายกัน

• กำหนดให้ $arr$ เป็นอาร์เรย์ที่ประกอบไปด้วยค่า $p_1 - 1, p_2 - 2, \dots, p_n - n$ และเรียงจากน้อยไปมาก และ $arr_i$ เป็นค่าของสมาชิกลำดับที่ $i$ ของ $arr$
• กำหนดให้ $rank(i)$ เท่ากับตำแหน่งของ $p_i - i$ ในอาร์เรย์ $arr$

เราจะทำการสร้าง Segment Tree จำนวน $2n$ ต้นที่รองรับการหาผลรวมเป็นช่วง ดังนี้

• สำหรับต้นที่ $i$ $(1 \leq i \leq n)$ ช่องที่ $j$ เราจะเก็บค่า $p_j - j$ เมื่อ $rank(j) \leq i$ มิเช่นนั้นจะเก็บค่า $0$
• สำหรับต้นที่ $n + i$ $(1 \leq i \leq n)$ ช่องที่ $j$ เราจะเก็บค่า $1$ เมื่อ $rank(j) \leq i$ มิเช่นนั้นจะเก็บค่า $0$

สังเกตว่าเราไม่จำเป็นต้องเก็บ Segment Tree ทั้ง $2n$ ต้นจริง ๆ เนื่องจากต้นที่ $i$ และ $i + 1$ หรือต้นที่ $n + i$ และ $n + i + 1$ จะมีสมาชิกใน Segment Tree ต่างกันเพียง 1 ตัวเท่านั้น ทำให้ใช้ Persistent Segment Tree เก็บข้อมูลเหล่านี้ได้

สำหรับการหาค่าของ $\sum \limits_{l \leq i \leq mid} min(p_i - i, 1 - l)$ เราจะแบ่งออกเป็นสองขั้นตอนได้แก่

1. หาผลรวมของ $p_i - i$ $(l \leq i \leq mid)$ เมื่อ $p_i - i \leq 1 - l$ โดย

   • กำหนดให้ $k$ เป็นจำนวนเต็มที่มากที่สุดที่ $arr_k \leq 1 - l$ สังเกตว่าสมาชิกของ Segment Tree ต้นที่ $k$ จะมีค่าไม่เกิน $1 - l$ เสมอ ทำให้เราหาผลรวมในขั้นตอนนี้มีค่าเท่ากับผลรวมช่วง $[l, r]$ ของ Segment Tree ต้นที่ $k$
   • กำหนดให้ค่าที่ได้ในขั้นตอนนี้เป็น $A$

2. นับจำนวน $i$ $(l \leq i \leq mid)$ ที่ $p_i - i > 1 - l$ ซึ่งหาได้จากการเอา $mid - l + 1$ หรือขนาดช่วงที่กำลังพิจารณา ลบออกด้วยผลรวมช่วง $[l, r]$ ใน Segment Tree ต้นที่ $n + k$ หรือจำนวน $i$ $(l \leq i \leq mid)$ ที่ $p_i - i \leq 1 - l$ นั่นเอง

   • กำหนดให้ค่าที่ได้ในขั้นตอนนี้เป็น $B$

จะได้ว่า $\sum \limits_{l \leq i \leq mid} min(p_i - i, 1 - l) = A + (1 - l)B$

ขั้นตอนดังกล่าวสามารถใช้ในการหาค่าของ $\sum \limits_{mid < i \leq r} min(p_i + i, 1 + r)$ ได้เช่นกัน ทำให้ใช้ Segment Tree ทั้งหมด $4n$ ต้น

นำค่าทั้งสองนี้รวมกับ $\frac{(l + mid)(mid - l + 1)}{2} - \frac{(mid + 1 + r)(r - mid)}{2}$ จะได้คำตอบของคำถามนั้น

สำหรับค่า $p_i$ นั้น เราสามารถหาได้ด้วยการทำ Binary Search + Rolling Hash

Time Complexity: $\mathcal{O}(n \log n)$