[DS记录]Loj#6198. 谢特
command_block
·
·
个人记录
题意 给出一个字符串 S ,每个位置都有一个权值 w_i。
定义两个后缀 i,j(i≠j) 的贡献为 lcp(i,j)+(w_i\ {\rm xor}\ w_j)。
求所有后缀对中的最大贡献。
------------
首先把串反过来,这样 $lcp$(前缀) 就变成了 $lcs$(后缀)。
然后建个`SAM`。
两个后缀 $i,j$ 的 $lcs$ 长度就相当于其在`parent`树上`LCA`的 $len$ 值。
在有根树上统计和 $lca$ 有关的信息,考虑链分治。
`dfs`这棵树,相当于在枚举`LCA`。启发式合并`01Trie`并计算最大的跨越当前`LCA`的$\rm xor$对子。
具体实现时,可以搜索轻子树得到需要合并的东西,此时要记录一下是否是前缀结尾位置,是才能贡献。
注意前缀结尾位置不一定是叶子,所以可能会在此处产生合并。
复杂度 $O(n\log^2n)$ ,然后就是码。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define MaxN 105000
using namespace std;
int read(){
int X=0;char ch=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
return X;
}
struct Node
{int t[26],f,len;}a[MaxN<<1];
int tot,las;
void add(int c)
{
int np=++tot,p=las;las=np;
a[np].len=a[p].len+1;
for (;p&&!a[p].t[c];p=a[p].f)a[p].t[c]=np;
if (!p)a[np].f=1;
else {
int v=a[p].t[c];
if (a[p].len+1==a[v].len)a[np].f=v;
else {
int nv=++tot;a[nv]=a[v];
a[nv].len=a[p].len+1;
for (;p&&a[p].t[c]==v;p=a[p].f)a[p].t[c]=nv;
a[v].f=a[np].f=nv;
}
}
}
vector<int> g[MaxN<<1];
int siz[MaxN<<1],p[MaxN<<1];
void pfs(int u)
{
siz[u]=1;
for (int i=0,v;i<g[u].size();i++){
pfs(v=g[u][i]);
siz[u]+=siz[v];
if (siz[v]>siz[p[u]])p[u]=v;
}
}
struct Data
{int l,r;}t[MaxN*19];
int rt[MaxN<<1],tn;
void build(int &rt,int x)
{
int u=rt=++tn;
for (int i=16;i>=0;i--){
if (x&(1<<i))t[u].r=++tn;
else t[u].l=++tn;
u=tn;
}
}
int merge(int x,int y)
{
if (!x||!y)return x|y;
t[x].l=merge(t[x].l,t[y].l);
t[x].r=merge(t[x].r,t[y].r);
return x;
}
int qry(int u,int x)
{
int ans=0;
for (int i=16;i>=0;i--)
if (x&(1<<i)){
if (t[u].l){u=t[u].l;ans^=(1<<i);}
else u=t[u].r;
}else {
if (t[u].r){u=t[u].r;ans^=(1<<i);}
else u=t[u].l;
}
return ans;
}
int ans,tp,tlen,w[MaxN<<1];
bool edp[MaxN<<1];
void dfs2(int u){
if (edp[u])
ans=max(ans,tlen+qry(tp,w[u]));
for (int i=0;i<g[u].size();i++)
dfs2(g[u][i]);
}
void dfs(int u)
{
if (!p[u])return ;
dfs(p[u]);
if (edp[u])
ans=max(ans,a[u].len+qry(rt[p[u]],w[u]));
rt[u]=merge(rt[u],rt[p[u]]);
for (int i=0,v;i<g[u].size();i++)
if ((v=g[u][i])!=p[u]){
tp=rt[u];tlen=a[u].len;
if (tp)dfs2(v);
dfs(v);rt[u]=merge(rt[u],rt[v]);
}
}
char s[MaxN];
int n,sw[MaxN];
int main()
{
scanf("%d%s",&n,s+1);
for (int i=1;i<=n;i++)scanf("%d",&sw[i]);
reverse(sw+1,sw+n+1);reverse(s+1,s+n+1);
tot=las=1;
for (int i=1;i<=n;i++)add(s[i]-'a');
for (int i=1,p=1;i<=n;i++){
p=a[p].t[s[i]-'a'];
build(rt[p],w[p]=sw[i]);
edp[p]=1;
}
for (int i=2;i<=tot;i++)
g[a[i].f].push_back(i);
pfs(1);dfs(1);
printf("%d",ans);
return 0;
}
```