回文自动机，时间充裕空间差最后两个点，死活卡不过，求教TAT

最终版代码：

#include<bits/stdc++.h>
using namespace std;
int n,tot,now;
string s;
struct hbr{
	int len,f,sw;
	long sp,ssp,ssw;
	unordered_map<short,int> t;
};
vector<hbr> a(2);
int getf(int u,int p){
	while(p-a[u].len-1<=0||s[p-a[u].len-1]!=s[p])u=a[u].f;
	return u;
}
pair<long,long> insert(int c,int id){
	int p=getf(now,id);
	if(!a[p].t[c]){
		a.emplace_back();
		a[++tot].f=a[getf(a[p].f,id)].t[c];
		a[p].t[c]=tot;
		a[tot].len=a[p].len+2;
		a[tot].sw=a[p].sw;
		a[tot].sp=a[p].sp+a[p].sw;
		if(c==26){
			a[tot].sw++;
			if(p!=1)a[tot].sw++;
			a[tot].sp+=a[tot].len-1;
		}
		a[tot].ssp=a[a[tot].f].ssp;
		a[tot].ssw=a[a[tot].f].ssw;
		if(a[tot].sw*2>=a[tot].len){
			a[tot].ssp+=a[tot].sp;
			a[tot].ssw+=a[tot].sw;
		}
	}
	now=a[p].t[c];
//	cout<<now<<' '<<p<<' '<<len[now]<<' '<<sw[now]<<' '<<sp[now]<<'\n';
	return {a[now].ssp,a[now].ssw};
}
void out(__int128 x){
	if(x==0)return;
	out(x/10);
	cout<<(short)(x%10);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	cin>>s;
	s=' '+s;
	a[0].f=1;
	a[++tot].len=-1;
	__int128 ans=0;
	for(int i=1;i<=n;i++){
		if(s[i]=='?')s[i]='z'+1;
		pair<long,long> o=insert(s[i]-'a',i);
		long p=o.first,w=o.second;
		ans+=i*w-p;
//		cout<<i*w-p<<'\n';
	}
	out(ans);
	return 0;
}