P9482 [NOI2023] 字符串

P9482 [NOI2023] 字符串

限制长的很像回文串，但是是字典序关系。

定睛一看比较的是原串 \(s\) 的一个后缀的前缀 和 翻转串 \(s'\) 的一个后缀的前缀比字典序。

直接把 \(s'\) 拼到 \(s\) 后面，中间加个分隔符，来一次后缀排序。排名小的后缀字典序比排名大的后缀小。

设当前比较的是 \([i,i+l-1]\) 和 \([i+l,i+2l-1]\)，两个串串长均为 \(l\)。

设 \(rk[i]\) 为 从 \(i\) 开始的后缀的排名。

那么我们要找到 \([i+l,i+2l-1]\) 在 \(s'\) 中对应的位置。在 \(s\) 与 \(s'\) 中插入一个分隔符的情况下，对应的区间将会是 \([2(n+1)-(i+2l-1),2(n+1)-(i+l)]\)。在不考虑 \([i,i+2l-1]\) 本身就是回文串的情况下，如果 \(rk[i]<rk[2(n+1)-(i+2l-1)]\) 那么这组 \((i,l)\) 合法。

可以发现，对于一个 \((i,r)\)，要与它比较的位置在\(s'\) 中的对应位置是 \(2(n+1)-(i+2x-1),1\le x\le r\)。是区间 \([2(n+1)-(i+2-1),2(n+1)-(i+2r-1)]\) 中所有奇数或者偶数。于是我们从排名大到小枚举后缀，按照起点位置奇偶性分别插入两棵树状数组，将询问挂在 \(i\) 上，枚举到 \(i\) 时进行区间查询即可。

接下来考虑去重，即 \([i,i+2l-1]\) 本身就是回文串的情况。

对于一个极长偶回文串 \([l,r]\)，回文中心为 \((p,p+1)\)。若 \(rk[l]<rk[2(n+1)-r]\) 即 \(l\) 开头的后缀排名比 \(r\) 在 \(s'\) 中对应位置开头的后缀排名小，那么在计算满足 \(l\le i\le p,i+r\ge p+1\) 的 \((i,r)\) 时会多算一次这个回文串（因为会算到 \(i\) 开头的这个回文串的一部分）。

我们用 manacher 先找出每个中心的极长偶回文串，然后将询问按照 \(i+r\) 排序，从小到大枚举并实时加入合法的回文中心 \(p\)，即将 \(p\) 所对应的 \([l,p]\) 区间加 1，然后查询 \(i\) 的单点值即为多算的数量。