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

#include <iostream>
#include <cstring>
#include <cstdio>
#define MAX 100000
using namespace std;

int manacher(int *s,int n) {
    int t[MAX * 2 + 2] = {-1,-1},p[MAX * 2 + 2];
    int c = 2;
    for(int i = 0;i < n;i ++) {
        t[c ++] = s[i];
        t[c ++] = -1;
    }
    int rp = 0,rrp = 0,ml = 0;
    for(int i = 1;i < c;i ++) {
        p[i] = i < rrp ? min(p[rp - (i - rp)],rrp - i) : 1;
        while(t[i + p[i]] == t[i - p[i]]) {
            if(i + p[i] < c && p[i] > 1 && (i + p[i]) % 2 == 0 && t[i + p[i]] > t[i + p[i] - 2]) break;
            p[i] ++;
        }
        if(rrp < i + p[i]) {
            rrp = i + p[i];
            rp = i;
        }
        if(ml < p[i]) {
            ml = p[i];
        }
    }
    return ml - 1;
}
int main() {
    int t,n,s[MAX];
    scanf("%d",&t);
    while(t --) {
        scanf("%d",&n);
        for(int i = 0;i < n;i ++) {
            scanf("%d",&s[i]);
        }
        printf("%d\n",manacher(s,n));
    }
}