【LOJ 6198】谢特 题解（可持久化Trie+后缀数组SA+启发式分裂+RMQ）
题外话
必备小芝士
可持久化Trie树模版：
https://www.luogu.com.cn/problem/P4735
后缀数组SA模板
https://www.luogu.com.cn/problem/P3809
RMQ模板
https://www.luogu.com.cn/problem/P2216
正题
题目传送门
https://loj.ac/p/6198
L
C
P
(
i
,
j
)
LCP(i,j)
LCP(i,j)的地方还是挺板的，没有什么思维含量 虽然单独拿出来扔洛谷上依然是道紫题
如果说
S
A
SA
SA不会，建议出门左转去做
S
A
SA
SA板子
然后
R
M
Q
RMQ
RMQ维护
以上只做出了这题的
5
%
5\%
5%
小学一年级都能想到关于之后的一个思路：
用单调栈维护一下
L
C
P
LCP
LCP，满足当前
L
C
P
LCP
LCP是一段连续区间中最小的。
我们可以轻松求出这段区间，然后没辙了
传统的基础做法就是
T
r
i
e
Trie
Trie，暴力无脑，对于数据的浪费量在动态使用下可想而知
这时候就要可持久化一下
网上有些教程说要先学可持久化线段树，其实可持久化 T r i e Trie Trie更为通俗易懂
这是传统的
T
r
i
e
Trie
Trie
这是在污染源数据的基础上增加的新边，可持久化的当然不会这么做
这样，我们只需要一条新链（防止污染源数据）即可，再用几条边连上原树即可（本图片略有勘误，黑色部分并非可持久化线段树）
查询直接减法即可
class trie{
private:
int ch[N*20][2],sum[N*20],tot;
public:
int root[N];
int insert(int s1,int v){
int s2=++tot,tmp=s2;
for (int i=16,t;i>=0;--i) {
ch[s2][0]=ch[s1][0];
ch[s2][1]=ch[s1][1];
sum[s2]=sum[s1]+1;
t=(v>>i)&1;
s1=ch[s1][t];
s2=ch[s2][t]=++tot;
}
sum[s2]=sum[s1]+1;
return tmp;
}
int query(int s1,int s2,int v){
int ans=0;
for(int i=16,t;i>=0;--i) {
t=((v>>i)&1)^1;
if(sum[ch[s2][t]]-sum[ch[s1][t]])
ans+=1<<i;
else
t^=1;
s1=ch[s1][t];
s2=ch[s2][t];
}
return ans;
}
}b;
但是，按照原思路，
i
i
i与
j
j
j都要在整个区域中查找，并不十分方便。
不难发现，有一部分查询是完全多余的，我们只需要查询
i
i
i于最小值左侧查找，
j
j
j于最小值右侧查找即可（否则最小值就不是该数了）
运用类似启发式合并的思想，不难发现，可以进行分治，从而可以取两侧长度中较短者进行枚举。由于较短者长度一定小于原来的一半，所以很容易发现复杂度是正确的（平均亦最坏复杂度
O
(
20
n
l
o
g
n
)
O(20nlogn)
O(20nlogn)，
20
20
20为可持久化
T
r
i
e
Trie
Trie常数）
该题得解
重难点
- R M Q RMQ RMQ与 S A SA SA板子要熟练
- 由于是存在原位置与后缀排名两个维度的，如果理不清楚可以直接在跑完 S A SA SA后把它们整理成一个维度，思维难度会降低；本题解并未这么做，所以较为繁琐
- 启发式分裂思想要掌握
- 可持久化数据结构要烂熟于心
- 在 h e i g h t height height上不要翻车（翻车了很容易怪罪到 R M Q RMQ RMQ上）
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
char x[N];
int n,w[N];
int rk[2*N],ork[2*N],st[N],lst[N],sa[N],cnt[N],id[N];
int ht[N];
int rmq[N][20],pos[N][20];
void get(){//获得sa、rk、height、RMQ
for(int i=1;i<=n;i++)
cnt[rk[i]=x[i]]++;
for(int i=0;i<127;i++)
cnt[i+1]+=cnt[i];
for(int i=n;i>=1;i--)
sa[cnt[rk[i]]--]=i;
int m=N-7,p=N-7;
for(int i=1;i<=n;i*=2,m=p){
for(int j=1;j<=n;j++)
ork[j]=rk[j];//j与j+i
int num=0;
for(int j=n-i+1;j<=n;j++)
id[++num]=j;
for(int j=1;j<=n;j++)
if(sa[j]>i){
id[++num]=sa[j]-i;
}
for(int j=0;j<=m;j++)
cnt[j]=0;
for(int j=1;j<=n;j++)
++cnt[ork[id[j]]];
for(int j=0;j<m;j++)
cnt[j+1]+=cnt[j];
for(int j=n;j>=1;j--){
sa[cnt[ork[id[j]]]--]=id[j];
}
p=0;
for(int j=1;j<=n;j++)
if(ork[sa[j]]==ork[sa[j-1]]&&ork[sa[j]+i]==ork[sa[j-1]+i])
rk[sa[j]]=p;
else
rk[sa[j]]=++p;
if(p==n)
break;
if(i>2)continue;
}
for(int i=1,j,k=0;i<=n;i++){
if(k)
--k;
if(rk[i]==n)continue;
j=sa[rk[i]+1];
while(x[i+k]==x[j+k])
++k;
ht[i]=k;
}
for(int i=1;i<n;i++)
rmq[i][0]=ht[sa[i]],
pos[i][0]=i;
for(int i=1;(1<<i)<n;i++)
for(int j=1;j+(1<<i)-1<n;j++){
if(rmq[j][i-1]<rmq[j+(1<<(i-1))][i-1])
pos[j][i]=pos[j][i-1];
else
pos[j][i]=pos[j+(1<<(i-1))][i-1];
rmq[j][i]=min(rmq[j][i-1],rmq[j+(1<<(i-1))][i-1]);
}
}
int getmin(int l,int r){//查找最小值
--r;
int x=log2(r-l+1);
if(rmq[l][x]<rmq[r-(1<<x)+1][x])
return pos[l][x];
else
return pos[r-(1<<x)+1][x];
}
class trie{//可持久化Trie树
private:
int ch[N*20][2],sum[N*20],tot;
public:
int root[N];
int insert(int s1,int v){
int s2=++tot,tmp=s2;
for (int i=16,t;i>=0;--i) {
ch[s2][0]=ch[s1][0];
ch[s2][1]=ch[s1][1];
sum[s2]=sum[s1]+1;
t=(v>>i)&1;
s1=ch[s1][t];
s2=ch[s2][t]=++tot;
}
sum[s2]=sum[s1]+1;
return tmp;
}
int query(int s1,int s2,int v){
int ans=0;
for(int i=16,t;i>=0;--i) {
t=((v>>i)&1)^1;
if(sum[ch[s2][t]]-sum[ch[s1][t]])
ans+=1<<i;
else
t^=1;
s1=ch[s1][t];
s2=ch[s2][t];
}
return ans;
}
}b;
int ans=0;
void solve(int l,int r){//启发式分裂
if(l>=r)
return;
int minpos=getmin(l,r);
int x,y,nl,nr;
if(minpos-l+1<r-minpos)
x=l,y=minpos,
nl=minpos+1,nr=r;
else
x=minpos+1,y=r,
nl=l,nr=minpos;
int mx=0;
for(int i=x;i<=y;++i)
mx=max(mx,b.query(b.root[nl-1],
b.root[nr],w[sa[i]]));
ans=max(ans,mx+ht[sa[minpos]]);
solve(l,minpos);
solve(minpos+1,r);
}
int main(){
ios::sync_with_stdio(0);
cin.tie();cout.tie();
cin>>n>>(x+1);
get();
for(int i=1;i<=n;i++)
cin>>w[i];
for(int i=1;i<=n;i++)
b.root[i]=b.insert(b.root[i-1],w[sa[i]]);
solve(1,n);
cout<<ans<<endl;
return 0;
}