洛谷 P4482 题解

nullqtr_pwp · 2026-01-24 10:11:11 · 题解

转化为求最小的 x>l 使得 \text{lcp}(suf_l,suf_x)\ge r-x+1。求后缀树，转化为 a_{\text{lca}(l,x)}\ge r-x+1，有 x\ge \max(r-a_{\text{lca}(x,l)}+1,l+1)。

对后缀树轻重链剖分，考虑 \text{lca} 是 l 跳轻边上来的，可以刻画为 \mathcal O(1) 个 dfn 区间上找标号后继，主席树做即可。否则 \text{lca} 落在每条重链的一段前缀上，将 \max(r-a_{u}+1,l+1) 拆开，由于 a 是从上往下单调的所以可以做，那么取到 l+1 的是一段区间，取到 r-a_u+1 的是一段前缀。

查询一段区间内 x\ge l+1 的最小 x 显然可以主席树。取到 r-a_u+1 的那段前缀，对这个前缀做扫描线，每次加入 x 形如将所有 x+a_u-1\ge r 的 r 的权值对 x 做 chkmin，然后在对应位置查询当前 r 的权值，可以树状数组维护。

每个重链上做的复杂度都是 \mathcal O(n\log n)，总时间复杂度 \mathcal O(n\log^2n)。