P16606 [SYSUCPC 2025] Palindrome

Recently, Student A has been studying strings. Certain peculiar strings caught his attention, so he named such strings ``quasi-palindromic strings``. A string $s$ is a quasi-palindromic string if and only if the following two conditions are both satisfied: 1. There does not exist any contiguous substring $t$ of $s$ with length greater than or equal to 2 that is a palindromic string. 2. Suppose the length of $s$ is $n$, there exist $l,r$ satisfying $1\leq l\leq r\leq n$, such that after reversing the substring $s[l...r]$, $s$ becomes a palindromic string. For example: The string ``aac`` is not a quasi-palindromic string because it contains the contiguous substring ``aa`` of length 2, which is a palindrome. The string ``abdc`` is not a quasi-palindromic string because there do not exist $l,r$ such that reversing the substring $s[l...r]$ would turn $s$ into a palindrome. The string ``bcabca`` is a quasi-palindromic string. Now, given a string $T$, Student A wants to know how many contiguous substrings of $T$ are quasi-palindromic strings. Here, contiguous substrings are distinguished solely by their starting and ending positions in the original string. For instance, in the string ``aba``, the contiguous substring [1,1] (the first ``a``) and the contiguous substring [3,3] (the last ``a``) are considered two different contiguous substrings, even though they are both the character ``a``.

A string $T(1\leq |T|\leq 5\times 10^5)$.

An integer representing the number of contiguous substrings of $T$ that are quasi-palindromic strings.

In the first sample, all contiguous substrings of length 1 are quasi-palindromic strings. Among substrings longer than 1, the quasi-palindromic strings are ``abcab``, ``bcabc``, and ``abcabc``.