【BZOJ2342】【SHOI2011】双倍回文

首先跑一遍manacher求出以每个间隙为中心的最长回文半径

那么若第\(x\)个间隙为中心,第二个\(w\)的结尾为第\(y\)个间隙,能够更新答案必然满足

右半边是回文串:\(y-len_y\le x\)

整个串是回文串:\(len_x\ge 2(y-x)\),即\(y\le x+\frac{len_x}{2}\)

那么我们可以将\(y-len_y\)排序不断加入,每次查询满足第二个条件的最大\(y\)值。用树状数组维护即可(当然要用set也行)。

说点什么

您将是第一位评论人!

提醒
wpDiscuz