XXXVI.LOJ#6198. 谢特
SA+笛卡尔树+01trie+启发式合并模板四合一，省选模板练习必备神器
考虑SA后建立笛卡尔树。问题转换为在笛卡尔树的一段区间中（此时该区间内任意两条后缀的LCP长度均为区间中 \(ht\) 最小值）任意两条后缀的 \(\text{xor}\) 最大值。是经典的01trie问题，考虑建立01trie。则，父节点的01trie可以由两个子节点的01trie启发式合并（或者说，因为笛卡尔树也是树，所以是dsu on tree）得到。
复杂度 \(O(n\log^2n)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m;
char s[100100];
int sa[100100],rk[100100],ht[100100],buc[100100];
bool mat(int a,int b,int k){
if(ht[a]!=ht[b])return false;
if((a+k<n)!=(b+k<n))return false;
if((a+k<n)&&(b+k<n))return ht[a+k]==ht[b+k];
return true;
}
void SA(){
for(int i=0;i<n;i++)buc[rk[i]=s[i]-'a']++;
for(int i=1;i<m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[rk[i]]]=i;
for(int k=1;k<n;k<<=1){
int num=0;
for(int i=n-k;i<n;i++)ht[num++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)ht[num++]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[rk[ht[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[rk[ht[i]]]]=ht[i],ht[i]=0;
swap(rk,ht),rk[sa[0]]=num=0;
for(int i=1;i<n;i++)rk[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
if(num>=n-1)break;
m=num;
}
for(int i=0;i<n;i++)ht[i]=0;
for(int i=0,k=0;i<n;i++){
if(!rk[i])continue;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
ht[rk[i]]=k;
}
}
int L[100100],R[100100],ls[100100],rs[100100],stk[100100],tp,res;
int a[100100],rt[100100],cnt,bin[10010000];
const int LG=17;
struct Trie{int ch[2];}t[10010000];
int newnode(){return tp?bin[tp--]:++cnt;}
void ins(int &x,int y,int pos){
if(!x)x=newnode();
if(pos==-1)return;
ins(t[x].ch[(y>>pos)&1],y,pos-1);
}
void erase(int &x){if(!x)return;bin[++tp]=x,erase(t[x].ch[0]),erase(t[x].ch[1]),x=0;}
int ask(int x,int y,int pos){
if(pos==-1)return 0;
if(t[x].ch[!((y>>pos)&1)])return ask(t[x].ch[!((y>>pos)&1)],y,pos-1)+(1<<pos);
else return ask(t[x].ch[(y>>pos)&1],y,pos-1);
}
int dfs(int x){
int ret=0;
if(ls[x])ret=max(ret,dfs(ls[x]));
if(rs[x])ret=max(ret,dfs(rs[x]));
if(x-L[x]>R[x]-x+1){
if(ls[x])rt[x]=rt[ls[x]];else ins(rt[x],a[sa[L[x]]],LG-1);
if(rs[x])erase(rt[rs[x]]);
for(int i=x;i<=R[x];i++)ret=max(ret,ask(rt[x],a[sa[i]],LG-1)),ins(rt[x],a[sa[i]],LG-1);
}else{
if(rs[x])rt[x]=rt[rs[x]];else ins(rt[x],a[sa[R[x]]],LG-1);
if(ls[x])erase(rt[ls[x]]);
for(int i=L[x];i<x;i++)ret=max(ret,ask(rt[x],a[sa[i]],LG-1)),ins(rt[x],a[sa[i]],LG-1);
}
res=max(res,ret+ht[x]);
return ret;
}
int main(){
scanf("%d%s",&n,s),m=26,SA();
// for(int i=0;i<n;i++)printf("%d ",i);puts("");
// for(int i=0;i<n;i++)printf("%d ",sa[i]);puts("");
// for(int i=0;i<n;i++)printf("%d ",rk[i]);puts("");
// for(int i=0;i<n;i++)printf("%d ",ht[i]);puts("");
// for(int i=0;i<n;i++)printf("%s\n",s+sa[i]);
for(int i=1;i<n;i++){
while(tp&&ht[stk[tp]]>ht[i])R[ls[i]=stk[tp--]]=i-1;
if(tp)L[i]=stk[tp];else L[i]=0;
rs[stk[tp]]=i,stk[++tp]=i;
}
while(tp)R[stk[tp--]]=n-1;
for(int i=0;i<n;i++)scanf("%d",&a[i]);
// for(int i=1;i<n;i++)printf("%d[%d,%d](%d,%d)\n",i,L[i],R[i],ls[i],rs[i]);
dfs(stk[1]),printf("%d\n",res);
return 0;
}