manacher回文串变形
本题要点：
1、此题把回文串的条件加强了，条件有3个：
a) 要求是回文串
b) 数值先递增，到了对称位置达到最大，然后递减。
2、 假如此类型的回文串叫做 “加强回文串”， 只需要在 manacher 函数里面，
改动一下 while 循环即可。
裸的 manacher算法， while 循环的条件
while(i - RL[i] >= 0 && i + RL[i] < len && ms[i - RL[i]] == ms[i + RL[i]])
{++RL[i];
}加强while 循环的条件
while(i - RL[i] >= 0 && i + RL[i] < m && (ms[i - RL[i]] == ms[i + RL[i]]) &&((i + RL[i]) % 2 == 0 || (i + RL[i] - 2 < i + 1 || ms[i + RL[i]] <= ms[i + RL[i] - 2])))
{RL[i]++;
}
增加了一个判断条件 (i + RL[i]) % 2 == 0 || (i + RL[i] - 2 < i + 1 || ms[i + RL[i]] <= ms[i + RL[i] - 2])
当前的下标是i， i + RL[i] 是当前能到达的最右端的下标，（ i + RL[i] 是偶数，表示是插入的数字0，不用管）
i + RL[i]是奇数的话， 先判断 i + RL[i] - 2 还在下标 i的右边， 然后就判断身高啦。 右边是递减的，
要满足 ms[i + RL[i]] <= ms[i + RL[i] - 2]
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN = 100010;
int s[MaxN], ms[MaxN * 2], RL[MaxN * 2];
int T, n;
int maxRight = 0, pos = 0, maxLen = 0;void manacher()
{
int m = n * 2 + 1;for(int i = 0; i < m; ++i){
if(i % 2 == 0) ms[i] = 0;else ms[i] = s[(i - 1) / 2];}maxRight = 0, pos = 0, maxLen = 0;for(int i = 0; i < m; ++i){
if(i < maxRight)RL[i] = min(RL[2 * pos - i], maxRight - i);elseRL[i] = 1;while(i - RL[i] >= 0 && i + RL[i] < m && (ms[i - RL[i]] == ms[i + RL[i]]) &&((i + RL[i]) % 2 == 0 || (i + RL[i] - 2 < i + 1 || ms[i + RL[i]] <= ms[i + RL[i] - 2]))){
RL[i]++; }if(RL[i] + i - 1 > maxRight){
maxRight = RL[i] + i - 1;pos = i;}maxLen = max(maxLen, RL[i]);
// printf("RL[%d] = %d\n", i, RL[i]);}printf("%d\n", maxLen - 1);
}int main()
{
scanf("%d", &T);while(T--){
scanf("%d", &n);for(int i = 0; i < n; ++i){
scanf("%d", &s[i]);}manacher();}return 0;
}/* 2 3 51 52 51 4 51 52 52 51 *//* 3 4 */