做题遇到了一个 trick，想了两天，求助教练，LLM 无果后，在大佬的帮助下明白了。
考虑以下 Manacher 代码的改版：
int n=s.size(),C=0,R=-1;
vector<int> p(n);
for(int i=0;i<n;i++){if(i<=R){//就是这样收缩int j=2*C-i;p[i]=p[j];while(p[i]>R-i+1) p[i]--;}else p[i]=1;while(i-p[i]>=0 && i+p[i]<n && s[i-p[i]]==s[i+p[i]]) p[i]++;int right=i+p[i]-1;if(right>=R) C=i,R=right;//是 >=，不是 >
}
其中相对于正常的 Manacher，将取 min 换成了朴素的收缩。这种改版，支持代码完成更多操作，减少数据结构的使用。
其实，这版代码的时间复杂度是线性的。
证明
考虑势能分析。
Manacher 一共扩张 \(O(n)\) 次，每次扩张会使一个 \(p\)（半径）值最多增加 \(1\)。
操作等效于：从 \(mid\)（最靠右回文串的对称轴）前面对称过来的回文串会先收缩到靠右回文串以内，再对称过来。
因为最多扩张 \(O(n)\) 次，所以只要每次收缩的回文串不是同一个，那么最多也只能收缩 \(O(n)\) 次。
如何保证？注意到代码倒数第二行的大于等于号，不难发现，如果出现需要收缩的情况，那么就算暴力扩展次数为 \(0\)，也一定会更新最靠右的回文串。于是每次收缩的回文串肯定不是同一个，证毕。
一道练习题
#include<bits/stdc++.h>
#define ll __int128
using namespace std;
/*
FACE THE FEAR, MAKE THE FUTURE.
P12977 泪雨 Namid[A]me
需要维护：括号数量，当前总贡献（合法子回文串括号数量之和），区间长度。
*/
const int N=5e6+7;
int n; string s;
ll p[N<<1],contr[N<<1],num[N<<1];
ll c,r,ans;int skl;void pre(){string t="$#";for(char ch:s) t+=ch,t+="#";t+="$"; s=t,n=s.size();
}void work(){for(int i=1;i<n;i++){if(i<=r){int j=2*c-i;while(p[j]>r-i+1){if(s[j+p[j]-1]=='#'&&num[j]*2>=p[j]-1) contr[j]-=num[j];if(s[j+p[j]-1]=='?') num[j]-=2;p[j]--;} contr[i]=contr[j],num[i]=num[j],p[i]=p[j];}else p[i]=1,num[i]=(s[i]=='?');while(s[i-p[i]]!='$'&&s[i+p[i]]!='$'&&s[i-p[i]]==s[i+p[i]]){num[i]+=2*(s[i+p[i]]=='?'); p[i]++;if(s[i+p[i]-1]=='#') contr[i]+=(2*num[i]>=p[i]-1)*num[i];}if(i+p[i]-1>=r) r=i+p[i]-1,c=i;ans+=contr[i]*i/2;}
}int main(){cin>>skl>>s;pre();work();if(ans==0) cout<<0;stack<int> stk;while(ans){stk.push(ans%10);ans/=10;} while(stk.size()) cout<<stk.top(),stk.pop();return 0;
}