思路

仿照 Manacher 的方法，在两个字符之间插入一个辅助字符。设插入后以第 $i$ 个字符为中心的最长回文半径为 $r_i$（注意不计入字符 $i$）。那么可以用并查集维护 $i+j,i-j(1\le j\le r_i)$ 的相同关系，建双向边维护 $i+r_i+1,i-r_i-1$ 的相异关系。这么做是 $O(n^2)$ 的。

接下来可以仿照 Manacher 的优化方式。记录已更新的右端点 $R$ 及其相对应的回文中心 $i$，那么 $i+1\sim R$ 中的回文中心 $i'$ 更新时，就不用处理 $j\le R-i'+1$ 的部分了。

构造时从左往右扫，如果与其相同的位置已填，则直接置为此字符，否则填满足限制的最小的字符即可。

这么做应该是 $O(nV\alpha(n))$ 的，其中 $V$ 为字符集大小。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,P=27;
int fa[N],siz[N];
int find(int x){
	if(x==fa[x]) return x;
    else return fa[x]=find(fa[x]);
}
void merge(int x,int y) {
	x=find(x),y=find(y);
	if(x==y) return;
    if(siz[y]<siz[x]) swap(x,y);
    if(siz[x]==siz[y]) siz[y]++;
    fa[x]=y;
}
vector<int> v[N];
bool fl[N][P];
int r[N],n;
int ml,mr;
int c[N],ans[N];
int main() {
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d",&r[2*i]);
	for(int i=1;i<=n-1;i++) scanf("%d",&r[2*i+1]);
	for(int i=1;i<=n;i++) fa[i]=i;
    ml=1,mr=0;
	for(int i=1;i<=n*2;i++) {
		int st=min(mr-i,r[ml+mr-i])+1;
		for(int j=st;j<=r[i];j++) {
			if((i-j)%2==0) merge((i-j)/2,(i+j)/2);
		}
		if(i+r[i]>mr) ml=i-r[i],mr=i+r[i];
		int lp=(i-r[i]-1)/2,rp=(i+r[i]+1)/2;
		v[lp].push_back(rp);
        v[rp].push_back(lp);
	}
	for(int i=1;i<=n;i++) {
		if(c[find(i)]) ans[i]=c[find(i)];
		else {
			for(int j=0;j<v[i].size();j++) fl[i][c[find(v[i][j])]]=1;
			for(int j=1;j<P;j++) {
				if(fl[i][j]==0) {
                    ans[i]=c[find(i)]=j;
                    break;
                }
			}
		}
	}
	for(int i=1;i<=n;i++) cout<<(char)(ans[i]+'a'-1);
}