LOJ6198谢特

思路是用后缀数组求出height 数组，在height数组中求出L,R数组表示左边第一个大于h[i]的位置+1和右边第一个大于h[i]的位置-1 根据 $\sum_{i=1}^n{\min(i-l+1,r-i+1)}$ 的值为 $n\log n$ 级别，可以枚举一个端点的值，用可持久化trie维护一个数和区间中数异或的最大值。

蒟蒻不知道为什么50pts，求大佬调

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define ll long long
#define pb emplace_back
int ff,Ch;
template <typename T> inline void rd(T &x) {
    x=0,ff=1,Ch=getchar();
    while((Ch<'0'||Ch>'9') && Ch!='-') Ch=getchar();
    if(Ch=='-')Ch=getchar(),ff=-1;
    while(Ch>='0' && Ch<='9') {
        x=(x<<1)+(x<<3)+Ch-'0';
        Ch=getchar();
    }
    x*=ff;
}
template <typename T,typename ...Args> inline void rd(T &x,Args &...args) {
    rd(x), rd(args...);
}
using namespace std;
const int N=2e5+5;
int n;
int val[N],h[N],L[N],R[N];
int stk[N],Top;
int sa[N],rk[N],oldrk[N];
bool check(int x,int y,int w) {
	return oldrk[x]==oldrk[y] && oldrk[x+w]==oldrk[y+w];
}
int rt[N],idx;
namespace trie {
	const int M=1e7+5;
	int ch[M][2],mx[M];
	void ins(int pos,int x,int y) {
		mx[x]=pos;
		for(int i=20,p; ~i; i--) {
			p=val[pos]>>i&1;
			if(y) ch[x][p^1]=ch[y][p^1];
			ch[x][p]=++idx;
			mx[idx]=pos;
			x=ch[x][p],y=ch[y][p];
		}
	}
	void init() {
		mx[0]=-1;
		rt[0]=++idx;
		ins(0,1,0);
	}
	int ask(int l,int r,int val) {
		int x=rt[r],ans=0;
		for(int i=20,p; ~i; i--) {
			p=val>>i&1;
			ans<<=1;
			if(mx[ch[x][p^1]]>=l)
				x=ch[x][p^1],ans|=(p^1);
			else x=ch[x][p],ans|=p;
		}
		return ans^val;
	}
}
signed main() {
#ifdef LOCAL
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
#endif
	IOS;
	string s;
    cin>>n>>s;
    s=" "+s;
    trie::init();
    for(int i=1; i<=n; i++) {
    	cin>>val[i];
    	sa[i]=i;
		rk[i]=s[i]; 
		rt[i]=++idx;
		trie::ins(i,rt[i],rt[i-1]);
	}	
	for(int w=1,p; w<n; w<<=1) {
		sort(sa+1,sa+1+n,[&](const int &x,const int &y) {
			return rk[x]<rk[y] || rk[x]==rk[y] && rk[x+w]<rk[y+w];
		});
		memcpy(oldrk,rk,sizeof(rk));
		p=0;
		for(int i=1; i<=n; i++) {
			if(check(sa[i],sa[i-1],w)) rk[sa[i]]=p;
			else rk[sa[i]]=++p;
		}
		if(p==n) break;
	}
	for(int i=1,k=0; i<=n; i++) {
		if(k) k--;
		while(s[i+k]==s[sa[rk[i]-1]+k]) k++;
		h[rk[i]]=k;
	}
	for(int i=1; i<=n; i++) {
		while(Top && h[i]<h[stk[Top]]) R[stk[Top--]]=i-1;
		L[i]=stk[Top]+1;
		stk[++Top]=i;
	}
	while(Top) R[stk[Top--]]=n;
	for(int i=1; i<=n; i++)
		assert(L[i] && L[i]<=i && i<=R[i] && R[i]);
//	for(int i=1; i<=n; i++)
//		cout<<L[i]<<' '<<R[i]<<'\n';
//	cout<<'\n';
	int ans=0;
	for(int i=1,pl,pr,ql,qr; i<=n; i++) {
		pl=L[i],pr=i,ql=i,qr=R[i];
		if(pr-pl+1>qr-ql+1) swap(pl,ql),swap(pr,qr);
		for(int j=pl; j<=pr; j++)
			ans=max(ans,trie::ask(ql,qr,val[j])+h[i]);
	}
	cout<<ans;
	return 0;
}
/*
1 2 3 4 5

2 3 4 5 6 7 9 10
*/