吉哥系列故事——完美队形II HDU - 4513

仍然可以说是Manacher算法的模板题
并不需要改动算法内部成分
我们需要对每个索引处再记录他到左边满足严格单调不递减的最大长度
然后遍历统计的时候，取小就可以了

另外这里我说一下，我觉得无论是kmp，扩展kmp，Manacher抑或是后缀数组

我们不要仅仅在特殊的一些运用上记住他们
事实上这种算法，他帮助我们维护的是一些包含字符串信息的数组
这些信息的存在使得我们可以解决一些复杂的问题

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int max_n = 1e5+100;
int n;

void Manacher(int a[],int d[],int b[]){
    for (int i=0,j=0;i<n;++i){
        b[j++]=-1;b[j++]=a[i];
    }
    int m = n*2+1;b[m-1]=-1;b[m]=-2;
    fill(d,d+m+5,1);
    for (int i=0,j=-1,t=0;i<m;++i){
        if (j>=i)d[i]=min(j-i+1,d[(t<<1)-i]);
        while (i+d[i]<m&&i-d[i]>=0&&b[i+d[i]]==b[i-d[i]])++d[i];
        if (i+d[i]>j)j=i+d[i]-1,t=i;
    }
}

int a[max_n],b[max_n<<1],d[max_n<<1],pre[max_n];
int main(){
    int T;scanf("%d",&T);
    while (T--){
        scanf("%d",&n);
        for (int i=0;i<n;++i)scanf("%d",&a[i]);
        pre[0]=1;
        for (int i=1;i<n;++i){
            if (a[i]>=a[i-1])pre[i]=pre[i-1]+1;
            else pre[i]=1;
        }
        Manacher(a,d,b);
        int ans = 0;
        for (int i=1;i<2*n;++i){
            if (i&1){
                ans = max(ans,min(d[i]>>1,pre[i>>1])*2-1);
            }
            else{
                ans = max(ans,min(d[i]>>1,pre[(i>>1)-1])*2);
            }
        }printf("%d\n",ans);
    }
}