分析
这些回文长度可以提供相等或者不等的信息,
不等的直接连边强制不等,相等用并查集合并连通块,
但是这样判断是\(O(n^2)\),考虑这些回文长度当用Manacher求时,
所有的回文长度都会在\(O(n)\)的时间内求出来,
所以可以模拟Manacher的过程完成上述操作,时间复杂度\(O(n)\)
代码
#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
const int N=100011; struct node{int y,next;}e[N<<2];
int p[N<<1],f[N],et=1,n,as[N],col[N],v[31],upd,Mx;
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline signed min(int a,int b){return a<b?a:b;}
inline signed getf(int u){return f[u]==u?u:f[u]=getf(f[u]);}
inline void Merge(int x,int y){
rr int fa=getf(x),fb=getf(y);
if (fa!=fb) f[fa]=fb;
}
inline void add(int x,int y){
e[++et]=(node){y,as[x]},as[x]=et;
e[++et]=(node){x,as[y]},as[y]=et;
}
signed main(){
n=iut(),Mx=n<<1|1,p[1]=p[Mx]=1;
for (rr int i=1;i<=n;++i) p[i<<1]=iut()+1;
for (rr int i=1;i<=n;++i) f[i]=i;
for (rr int i=1;i<n;++i) p[i<<1|1]=iut()+1;
rr int mid=1,mx=1;
for (rr int i=2;i<=n*2;++i){
rr int now=i<mx?min(p[mid*2-i],mx-i):1;
for (rr int j=now;j<p[i];++j)
if (!((i-j)&1)&&!((i+j)&1))
Merge((i-j)>>1,(i+j)>>1);
if (p[i]<i&&i+p[i]<=Mx) add((i-p[i])>>1,(i+p[i])>>1);
if (i+p[i]-1>mx) mid=i,mx=i+p[i]-1;
}
for (rr int i=1;i<=n;++i)
if (!col[getf(i)]){
v[0]=++upd;
for (rr int j=as[i];j;j=e[j].next)
if (e[j].y) v[col[getf(e[j].y)]]=upd;
while (v[col[getf(i)]]==upd) ++col[getf(i)];
}
for (rr int i=1;i<=n;++i) putchar(col[getf(i)]+96);
return 0;
}