P14830 [THUPC 2026 初赛] 回响形态

草，刚刚发现赛时 border \(p\) 数组没清空，气笑了。

根据 P3546 中的 trick，将字符串变为 \(s_1s_ns_2s_{n-1}...\) 后，border 变为开头的回文串。发现这题 \([l,r]\) 从中心向两边拓展实际上为在字符串开头添加两个字符，所以转化后成了以 \(i\)，满足 \(i\) 为奇数，\(\frac{i}{2}\) 为偶数的位置开头的偶回文串。比较特殊的是这题 border 能跨过中点，P3546 不行，只需要改一下，将完整的正反串交替，只查询前半部分表示 border 开头必须在前半部分即可。

数据范围支持每次跑一遍 manacher，所以 \(O(nq)\) 即可。

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define cfast ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define ll long long
inline int lowbit(int x){return x&-x;}
const int N=4e6+5;
int p[N];ll c[N],ans;
inline void manacher(string t){string s="^";for(int i=0;i<t.size();i++)s+='$',s+=t[i];s+="$)";int id,R=0,len=s.size();for(int i=1;i<len;i++){p[i]=1;if(i<=R)p[i]=min(p[(id<<1)-i],R-i+1);int l=i-p[i],r=i+p[i];while(s[l]==s[r])--l,++r,++p[i];if(i+p[i]-1>R)R=i+p[i]-1,id=i;}for(int i=1;i<=len/2;i+=2)++c[i-p[i]+1],--c[i];for(int i=1;i<=len/2;i++){c[i]+=c[i-1];if(!(i&1)&&((i>>1)&1))ans+=c[i];}for(int i=0;i<len/2;i++)c[i]=0;
}
inline void UesugiErii(){int n,q;string s;cin>>n>>q>>s,s=' '+s;while(q--){int k,l,r,x,y;string tmp="";cin>>k;if(k&1)y=(k+1)/2,x=y-1;else x=k/2-1,y=k/2+1; for(l=x,r=y;l>=1&&r<=n;--l,++r);++l,--r;for(int i=l,j=r;i<=r;++i,--j)tmp+=s[i],tmp+=s[j];ans=0,manacher(tmp);cout<<ans<<'\n';}
}
signed main(){//freopen(".in","r",stdin);//freopen(".out","w",stdout);cfast;int _=1;//cin>>_;for(;_;_--)UesugiErii();return 0;
}