题解：P5115 Check,Check,Check one two!

szh_AK_all · 2025-04-10 07:03:11 · 题解

摘自本文。

P5115 Check,Check,Check one two!

记 f_x=\sum_{l=1}^{k_1} \sum_{r=1}^{k_2}[l+r-1=x]\times l\times r，则我们要求的式子可以转化成 \sum_{i=1}^n \sum_{j=i+1}^n [s_{i-1}\ne s_{j-1}]\times f_{lcp(rk_i,rk_j)}，转而枚举 lcp，即 \sum_{i=1}^n f_i\times \sum_{i=1}^n \sum_{j=i+1}^n [lcp(rk_i,rk_j)=k]\times [s_{i-1}\ne s_{j-1}]，也就是 \sum_{i=1}^n f_i\times \sum_{i=1}^n \sum_{j=i+1}^n[lcp(i,j)=k]\times [s_{sa_i-1}\ne s_{sa_j-1}]。

那么可以考虑枚举每个 lcp 计算其对答案的贡献。

我们仍然可以对 height 数组建出笛卡尔树，对于当前点 x，从它的左右区间所涵盖的后缀范围内各任选一个后缀，则他们的 lcp 为 h_x。但是我们从左右子树选出节点 i,j 后，还需满足 s_{sa_i-1}\ne s_{sa_j-1}，显然某个 s_k 只有 26 种取值，于是可以设 g_{i,j} 表示在节点 i 的子树中满足 sa_{sa_y-1}=j 的 y 的个数。转移有 g_{x,i}=g_{lson,i}+g_{rson,i}，对答案的贡献为 \sum_{i\ne j} g_{lson,i}\times g_{rson,j}，这个是好算的。

考虑计算 f_x。