Description：

给出一个串，每次询问一个区间中有多少个回文子串，位置不同算不同。

$1\leqslant n\leqslant 10^5$

Solution：

先像 $manacher$ 那样补特殊字符，然后对于在前半部分和后半部分的回文串分类讨论，显然答案为： $$ \begin{align} ans=\sum_{i=l}^r\min(\min(r[i]-x[i],x[i]-l[i]),h[i])\\ \end{align} $$ 每个位置分在询问区间前半部分和后半部分分别计算就可以用主席树维护一下。

Code：

没有代码