两天了，终于把这题调出来了（
一堆沙雕错误……
看见后缀的 \(\text{LCP}\)，第一反应当然是 SA 啦！
于是考虑求出 SA 和 height 先。
众所周知题目中定义的 \(\text{LCP}(i,j) = \min\limits_{i = rank_l + 1}^{rank_r} height_i\)。
这让我联想到了 Beautiful Pair 那一题的套路——以区间最值进行分治，又称为「启发式分裂」。
即，对于 height 数组分治。并在分治的时候，取最值所在点为中点，然后枚举中点以左 / 以右两段中长度较短的一段，并用数据结构取得另一段对应的答案。
对于此题应当使用可持久化 Trie。
于是就很套路了，但我还调了这么久……
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
using namespace std;
const int N = 1e5;
const int LG = 17;
int n,w[N + 5],lg2[N + 5];
char a[N + 5];
int sa[N + 5],rk[N + 5],tpr[N + 5],c[N + 5],height[N + 5];
int st[N + 5][LG + 5];
void build_SA()
{
static int m = 127;
memset(c,0,sizeof c);
for(register int i = 1;i <= n;++i)
++c[rk[i] = a[i]];
for(register int i = 1;i <= m;++i)
c[i] += c[i - 1];
for(register int i = n;i;--i)
sa[c[rk[i]]--] = i;
for(register int w = 1,p = 0;p < n;w <<= 1,m = p)
{
p = 0;
for(register int i = 1;i <= w;++i)
tpr[++p] = n - w + i;
for(register int i = 1;i <= n;++i)
if(sa[i] > w)
tpr[++p] = sa[i] - w;
memset(c,0,sizeof c);
for(register int i = 1;i <= n;++i)
++c[rk[i]];
for(register int i = 1;i <= m;++i)
c[i] += c[i - 1];
for(register int i = n;i;--i)
sa[c[rk[tpr[i]]]--] = tpr[i];
swap(rk,tpr),rk[sa[1]] = p = 1;
for(register int i = 2;i <= n;++i)
rk[sa[i]] = tpr[sa[i]] == tpr[sa[i - 1]] && tpr[sa[i] + w] == tpr[sa[i - 1] + w] ? p : ++p;
}
for(register int i = 1,k = 0;i <= n;++i)
{
k -= (bool)k;
for(;a[i + k] == a[sa[rk[i] - 1] + k];++k);
height[rk[i]] = k;
}
}
struct node
{
int ch[2];
int ed;
} trie[(N << 5) + 10];
int rt[N + 5];
void insert(int x,int k,int &p)
{
static int tot = 0;
trie[++tot] = trie[p],trie[tot].ed = x;
p = tot;
int cur = p;
for(register int i = LG;i;--i)
{
trie[++tot] = trie[trie[cur].ch[(k >> i - 1) & 1]],trie[tot].ed = x;
trie[cur].ch[(k >> i - 1) & 1] = tot;
cur = trie[cur].ch[(k >> i - 1) & 1];
}
}
int query(int x,int k,int p)
{
int ret = 0;
int cur = p;
for(register int i = LG;i;--i)
if(trie[trie[cur].ch[((k >> i - 1) & 1) ^ 1]].ed >= x)
{
ret += 1 << i - 1;
cur = trie[cur].ch[((k >> i - 1) & 1) ^ 1];
}
else
cur = trie[cur].ch[(k >> i - 1) & 1];
return ret;
}
int query_min(int l,int r)
{
int lg = lg2[r - l + 1];
return height[st[l][lg]] <= height[st[r - (1 << lg) + 1][lg]] ? st[l][lg] : st[r - (1 << lg) + 1][lg];
}
int solve(int l,int r)
{
if(l >= r)
return 0;
int ret = 0;
int mn = query_min(l + 1,r);
if(r - mn + 1 < mn - l)
for(register int i = mn;i <= r;++i)
ret = max(ret,height[mn] + query(l,w[sa[i]],rt[mn - 1]));
else
for(register int i = l;i < mn;++i)
ret = max(ret,height[mn] + query(mn,w[sa[i]],rt[r]));
return max(ret,max(solve(l,mn - 1),solve(mn,r)));
}
int main()
{
scanf("%d",&n);
for(register int i = 1;i <= n;++i)
st[i][0] = i;
for(register int i = 2;i <= n;++i)
lg2[i] = lg2[i / 2] + 1;
scanf("%s",a + 1);
build_SA();
for(register int i = 1;i <= LG;++i)
for(register int j = 1;j + (1 << i) - 1 <= n;++j)
if(height[st[j][i - 1]] <= height[st[j + (1 << i - 1)][i - 1]])
st[j][i] = st[j][i - 1];
else
st[j][i] = st[j + (1 << i - 1)][i - 1];
for(register int i = 1;i <= n;++i)
scanf("%d",w + i);
for(register int i = 1;i <= n;++i)
insert(i,w[sa[i]],rt[i] = rt[i - 1]);
printf("%d\n",solve(1,n));
}