P6640 [BJOI2020]封印 题解
题面
对 \(T\) 建 SAM，拿 \(S\) 进去跑，可以得到每个 \(S\) 的前缀 \(S_i\) 的最长匹配后缀长度 \(sl_i\)。那么对于一个询问 \([l,r]\)，答案就是 \(\max_{l\leq i\leq r}\{\min(sl_i,i-l+1)\}\)。
里面这个 \(\min\) 很难解决，我们考虑二分答案长度 \(mid\)，这样就可以只询问 \([l+mid-1,r]\) 的 \(sl_i\) 的 \(\max\)，这个使用 ST 表可以 \(O(1)\) 解决。总复杂度 \(O(n|\Sigma|\log n)\)。
点击查看代码
const int N=2e5+13;
namespace ST{
#define f _st
#define ccf log2
const int logN=21;
int f[N][logN],log2[N];
inline void init(int n){
for(int i=1;i<=n;++i) log2[i]=log2[i>>1]+1;
int k=log2[n];
for(int j=1;j<=k;++j)
for(int i=1;i+(1<>1;
if(ST::query(L+mid-1,R)>=mid) l=mid;
else r=mid-1;
}
println(l);
}
return 0;
}