就好比第一次写主席树的时候写了30行，第二次写了5行
这次马拉车只剩下
1 for(int i=1,id=0,mx=0;i<=n;i++) 2 { 3 for(p[i]=(i<=mx)?min(p[id*2-i],mx-i):0;a[i-p[i]]==a[i+p[i]+1];p[i]++); 4 if(p[i]+i>mx) id=i,mx=i+p[i]; 5 }
（= =缩代码狂魔）
这次不要求奇偶讨论，所以连#都没插，注意在最后统计的时候可以用stl的特殊姿势
1 #include <cstdio> 2 #include <algorithm> 3 #include <set> 4 using namespace std; 5 int n,u,v,ans,p[500001],q[500001],nex[500001],fir[500001]; 6 char a[500001]; 7 set<int> t; 8 inline int min(int a,int b){return (a<b)?a:b;} 9 inline int max(int a,int b){return (a>b)?a:b;} 10 bool cmp(int a,int b) 11 { 12 return (a-p[a])<(b-p[b]); 13 } 14 int main() 15 { 16 scanf("%d",&n); 17 char ch=getchar(); 18 while(ch<'a' || ch>'z') ch=getchar(); 19 for(int i=1;i<=n;ch=getchar()) 20 a[i++]=ch; 21 for(int i=1,id=0,mx=0;i<=n;i++) 22 { 23 for(p[i]=(i<=mx)?min(p[id*2-i],mx-i):0;a[i-p[i]]==a[i+p[i]+1];p[i]++); 24 if(p[i]+i>mx) id=i,mx=i+p[i]; 25 } 26 for(int i=1;i<=n;i++)q[i]=i; 27 sort(q+1,q+n+1,cmp); 28 int now=1; 29 for(int i=1;i<=n;i++) 30 { 31 while(now<=n&&q[now]-p[q[now]]<=i) 32 { 33 t.insert(q[now]); 34 now++; 35 } 36 set<int>::iterator tmp=t.upper_bound(i+p[i]/2); 37 if(tmp!=t.begin()) 38 { 39 ans=max(ans,(*--tmp-i)*4); 40 } 41 } 42 printf("%d ",ans); 43 return 0; 44 }
马拉车差不多告一段落（以后肯定还要返工）接下来再做点网络流吧