其他字符串算法学习笔记 收藏防迷路

欧清辣哨

[backcolor=rgba(255, 255, 255, 0.5)]关于字符串Hash和后缀自动机SAM可以转至我之前的博客，这里不再阐述。

[backcolor=rgba(255, 255, 255, 0.5)]这里主要介绍一些不怎么常用（至少不如SAM和Hash）的算法。

1.SA

[backcolor=rgba(255, 255, 255, 0.5)]模拟退火后缀数组（Suffix Array）是一种很奇妙的算法。主要原因是它可以做到在 <span class="MathJax" id="MathJax-Element-1-Frame" tabindex="0" data-mathml="O(nlog&#x2061;n)" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">O(nlogn)O(nlog&#8289;n) 时间内完成排序。

[backcolor=rgba(255, 255, 255, 0.5)]关于如何完成这个比较基础，具体可见洛谷日报。

[backcolor=rgba(255, 255, 255, 0.5)]而后缀排序的重点在于“字典序排序”的一些奇妙性质。所以对于一般字符串的字典序排序，以下性质也适用。

[backcolor=rgba(255, 255, 255, 0.5)]首先可以发现的是 <span class="MathJax" id="MathJax-Element-2-Frame" tabindex="0" data-mathml="LCP&#x2061;(i,j)=min(LCP&#x2061;(i,k),LCP&#x2061;(k,j)),k&#x2208;[i,j]" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">LCP(i,j)=min(LCP(i,k),LCP(k,j)),k∈[i,j]LCP&#8289;(i,j)=min(LCP&#8289;(i,k),LCP&#8289;(k,j)),k∈[i,j]。这个比较显然主要我也不怎么会严格证明。具体可以见洛谷日报的证明。

[backcolor=rgba(255, 255, 255, 0.5)]考虑有了这个我们可以干什么。考虑这样一道题：按一定方式给定一堆字符串（总长度可能很大），问其中本质不同前缀的个数。

[backcolor=rgba(255, 255, 255, 0.5)]那么显然可以发现，相邻两字符串的 <span class="MathJax" id="MathJax-Element-3-Frame" tabindex="0" data-mathml="LCP" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">LCPLCP 就是他们本质相同的前缀。换句话说，除此之外的部分都是本质不同的。

[backcolor=rgba(255, 255, 255, 0.5)]而根据那个奇怪的性质，相邻两个字符串 <span class="MathJax" id="MathJax-Element-4-Frame" tabindex="0" data-mathml="(x,x+1)" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">(x,x+1)(x,x+1) 的 <span class="MathJax" id="MathJax-Element-5-Frame" tabindex="0" data-mathml="LCP" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">LCPLCP 一定 <span class="MathJax" id="MathJax-Element-6-Frame" tabindex="0" data-mathml="&#x2265;(i,k),k&#x2265;i+1" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">≥(i,k),k≥i+1≥(i,k),k≥i+1 的 <span class="MathJax" id="MathJax-Element-7-Frame" tabindex="0" data-mathml="LCP" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">LCPLCP。所以显然成立。

[backcolor=rgba(255, 255, 255, 0.5)]但是这个相邻的 <span class="MathJax" id="MathJax-Element-8-Frame" tabindex="0" data-mathml="LCP" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">LCPLCP 怎么求呢？

[backcolor=rgba(255, 255, 255, 0.5)]其实是有一个很simple的 <span class="MathJax" id="MathJax-Element-9-Frame" tabindex="0" data-mathml="O(n)" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">O(n)O(n) 求法。什么SA-IS？完全不会。

[backcolor=rgba(255, 255, 255, 0.5)]具体来说，我们可以求出第 <span class="MathJax" id="MathJax-Element-10-Frame" tabindex="0" data-mathml="i" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">ii 个位置与字典序在它前面的串的 <span class="MathJax" id="MathJax-Element-11-Frame" tabindex="0" data-mathml="LCP" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">LCPLCP <span class="MathJax" id="MathJax-Element-12-Frame" tabindex="0" data-mathml="hi" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">hihi。可以发现有 <span class="MathJax" id="MathJax-Element-13-Frame" tabindex="0" data-mathml="hi=hi&#x2212;1+1" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">hi=hi&#8722;1+1hi=hi&#8722;1+1。于是乎就均摊 <span class="MathJax" id="MathJax-Element-14-Frame" tabindex="0" data-mathml="O(n)" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">O(n)O(n) 了。

[backcolor=rgba(255, 255, 255, 0.5)]那么我们可以做什么了呢？求本质不同子串！每个后缀的前缀唯一对应一个子串，所以直接减就好了。

[backcolor=rgba(255, 255, 255, 0.5)]例：本质不同子串

#include<iostream>#include<cstdio>#include<cstring>#define N 100010using namespace std;int b[N],sa[N],rk[N],a[N],id[N];char s[N];void SA_(int n,int m){        for(int i=0;i<=m;i++) b=0;        for(int i=1;i<=n;i++) b[rk]++;        for(int i=1;i<=m;i++) b+=b[i-1];        for(int i=n;i>=1;i--) sa[b[rk[id]]--]=id;}void SA(int n){        int m=124;        for(int i=1;i<=n;i++) rk=s-'0'+1,id=i;        SA_(n,m);int t=0;        for(int p=1;p<n;m=t,t=0,p<<=1)        {                for(int i=1;i<=p;i++) id[++t]=n-p+i;                for(int i=1;i<=n;i++) if(sa>p) id[++t]=sa-p;                SA_(n,m); swap(id,rk); rk[sa[1]]=t=1;                for(int i=2;i<=n;i++) rk[sa]=(t+=id[sa[i-1]]!=id[sa] || id[sa[i-1]+p]!=id[sa+p]);        }}int ht[N];void get_ht(int n){        for(int i=1,p=0;i<=n;ht[rk]=p,i++)        if(rk!=1) for(p=p-!!p;sa[rk-1]+p<=n && i+p<=n && s[i+p]==s[sa[rk-1]+p];p++);}int main(){        int n;        scanf("%d%s",&n,s+1);        SA(n);        get_ht(n);        long long ans=1ll*n*(n+1)/2;        for(int i=1;i<=n;i++) ans-=ht;        printf("%lld\n",ans);        return 0;}// 压行？怎么可能？这叫 建筑美（

[backcolor=rgba(255, 255, 255, 0.5)]看到这你或许会问：这个不是SAM也能做吗？而且SAM是 <span class="MathJax" id="MathJax-Element-15-Frame" tabindex="0" data-mathml="O(n)" role="presentation" style="display: inline; font-weight: normal; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">O(n)O(n) 的。

[backcolor=rgba(255, 255, 255, 0.5)]的确，绝大部分SA能做的SAM都能做，而且SAM跑得快、支持在线、还更好些（所以我学SA干什么）。

[backcolor=rgba(255, 255, 255, 0.5)]别急，这里还有一个SA的晋升版本：

2.后缀平衡树（好像不一定是这么叫的）

[backcolor=rgba(255, 255, 255, 0.5)]没想到吧，后缀平衡树居然不是后缀树变过来的（我也没想到）。

[backcolor=rgba(255, 255, 255, 0.5)]首先我们还是考虑一般情况：给定一个字符串 <span class="MathJax" id="MathJax-Element-16-Frame" tabindex="0" data-mathml="S" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">SS 的一堆子串，每次问某个子串 <span class="MathJax" id="MathJax-Element-17-Frame" tabindex="0" data-mathml="s0" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">s0s0 与其他每个串的 <span class="MathJax" id="MathJax-Element-18-Frame" tabindex="0" data-mathml="LCP" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">LCPLCP 最大是多少。动态修改子串集合。

[backcolor=rgba(255, 255, 255, 0.5)]这个可以怎么做？考虑使用平衡树套Hash。具体可以见Hash学习笔记中的一道口胡的题（里面好像还有一个强制在线）。

[backcolor=rgba(255, 255, 255, 0.5)]这个是 <span class="MathJax" id="MathJax-Element-19-Frame" tabindex="0" data-mathml="O(nlog2&#x2061;n)" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">O(nlog2n)O(nlog2&#8289;n) 的，虽然比较暴力已经足够优秀了。但是如果我们插入的字符串有一些规律可循，是不是有更快的做法。

【模板】后缀平衡树题意

[backcolor=rgba(255, 255, 255, 0.5)]维护一个字符串，支持加一堆字符，删一堆字符，询问某个字符出现次数。强制在线。总字符长度 <span class="MathJax" id="MathJax-Element-20-Frame" tabindex="0" data-mathml="&#x2264;106" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">≤106≤106。

[backcolor=rgba(255, 255, 255, 0.5)]出题人真的是丧心病狂。。。

[backcolor=rgba(255, 255, 255, 0.5)]AC自动机能过？那就强制在线。

[backcolor=rgba(255, 255, 255, 0.5)]SAM还能过？那就每次加一堆字符。

[backcolor=rgba(255, 255, 255, 0.5)]啥？两只 <span class="MathJax" id="MathJax-Element-21-Frame" tabindex="0" data-mathml="log" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">loglog 艹过去了？那就开到 <span class="MathJax" id="MathJax-Element-22-Frame" tabindex="0" data-mathml="106" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">106106。真·5步出题法。

[backcolor=rgba(255, 255, 255, 0.5)]显然我们需要一个更高妙的做法。考虑多一只 <span class="MathJax" id="MathJax-Element-23-Frame" tabindex="0" data-mathml="log" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">loglog 的瓶颈在于每次判断字典序时必须 <span class="MathJax" id="MathJax-Element-24-Frame" tabindex="0" data-mathml="O(log&#x2061;n)" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">O(logn)O(log&#8289;n) 处理。再加上判断 <span class="MathJax" id="MathJax-Element-25-Frame" tabindex="0" data-mathml="O(log&#x2061;n)" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">O(logn)O(log&#8289;n) 次，所以总 <span class="MathJax" id="MathJax-Element-26-Frame" tabindex="0" data-mathml="O(log2&#x2061;n)" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">O(log2n)O(log2&#8289;n)。

[backcolor=rgba(255, 255, 255, 0.5)]平衡树的 <span class="MathJax" id="MathJax-Element-27-Frame" tabindex="0" data-mathml="log&#x2061;n" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">lognlog&#8289;n 没办法优化，考虑优化判断字典序。可以发现，我们要加入的字符串 <span class="MathJax" id="MathJax-Element-28-Frame" tabindex="0" data-mathml="u" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">uu 在加入前它的前缀一定已经出现过了，所以前缀和当前要比较的节点 <span class="MathJax" id="MathJax-Element-29-Frame" tabindex="0" data-mathml="p" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">pp 均出现过。

[backcolor=rgba(255, 255, 255, 0.5)]可以发现，当前加入的字符串 <span class="MathJax" id="MathJax-Element-30-Frame" tabindex="0" data-mathml="u" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">uu 除了最后一个字符之外其他都与前缀 <span class="MathJax" id="MathJax-Element-31-Frame" tabindex="0" data-mathml="u&#x2212;1" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">u&#8722;1u&#8722;1 完全一致，所以我们先暴力比较 <span class="MathJax" id="MathJax-Element-32-Frame" tabindex="0" data-mathml="u" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">uu 与 <span class="MathJax" id="MathJax-Element-33-Frame" tabindex="0" data-mathml="p" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">pp 的最后一个字符，如果相同意味着这个 <span class="MathJax" id="MathJax-Element-34-Frame" tabindex="0" data-mathml="u&#x2212;1" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">u&#8722;1u&#8722;1 和 <span class="MathJax" id="MathJax-Element-35-Frame" tabindex="0" data-mathml="p&#x2212;1" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">p&#8722;1p&#8722;1 的字典顺序决定了 <span class="MathJax" id="MathJax-Element-36-Frame" tabindex="0" data-mathml="u" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">uu 与 <span class="MathJax" id="MathJax-Element-37-Frame" tabindex="0" data-mathml="p" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">pp 的字典顺序。但是直接这样比较还是 <span class="MathJax" id="MathJax-Element-38-Frame" tabindex="0" data-mathml="O(log&#x2061;n)" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">O(logn)O(log&#8289;n)。

[backcolor=rgba(255, 255, 255, 0.5)]考虑如果我们维护出了所有前缀的 <span class="MathJax" id="MathJax-Element-39-Frame" tabindex="0" data-mathml="rank" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">rankrank，那么显然 <span class="MathJax" id="MathJax-Element-40-Frame" tabindex="0" data-mathml="rank" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">rankrank 的相对顺序就对应最后的结果。但是我们不能直接维护rank，这样会平白多出一个 <span class="MathJax" id="MathJax-Element-41-Frame" tabindex="0" data-mathml="log&#x2061;n" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">lognlog&#8289;n。考虑我们只需要知道 <span class="MathJax" id="MathJax-Element-42-Frame" tabindex="0" data-mathml="rank" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">rankrank 的相对顺序即可。考虑利用平衡树的性质，每个点取一个权值 <span class="MathJax" id="MathJax-Element-43-Frame" tabindex="0" data-mathml="vi=L+R2" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">vi=L+R2vi=L+R2，然后根据 <span class="MathJax" id="MathJax-Element-44-Frame" tabindex="0" data-mathml="vi" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">vivi 将区间分为两段递归处理。可以发现，这样满足 <span class="MathJax" id="MathJax-Element-45-Frame" tabindex="0" data-mathml="vlsu&lt;vu&lt;vrsu" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">vlsu<vu<vrsuvlsu<vu<vrsu。

[backcolor=rgba(255, 255, 255, 0.5)]这样建树的时间复杂度 <span class="MathJax" id="MathJax-Element-46-Frame" tabindex="0" data-mathml="O(|S|log&#x2061;|S|)" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">O(|S|log|S|)O(|S|log&#8289;|S|)。

[backcolor=rgba(255, 255, 255, 0.5)]考虑这题维护的东西：出现次数。

[backcolor=rgba(255, 255, 255, 0.5)]这个就很好办了。考虑差分，比如要查 <span class="MathJax" id="MathJax-Element-47-Frame" tabindex="0" data-mathml="AB" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">ABAB，我们就查字典序在 <span class="MathJax" id="MathJax-Element-48-Frame" tabindex="0" data-mathml="AA[" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">AA[AA[ 和 <span class="MathJax" id="MathJax-Element-49-Frame" tabindex="0" data-mathml="AB[" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">AB[AB[ 之间的字符。（<span class="MathJax" id="MathJax-Element-50-Frame" tabindex="0" data-mathml="[" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">[[ 的字典序大于所有大写字母）。具体来说，由于后缀平衡树中不存在字符 <span class="MathJax" id="MathJax-Element-51-Frame" tabindex="0" data-mathml="[" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">[[ ，我们可以直接用字典序小于 <span class="MathJax" id="MathJax-Element-52-Frame" tabindex="0" data-mathml="AB[" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">AB[AB[ 的数量减去小于 <span class="MathJax" id="MathJax-Element-53-Frame" tabindex="0" data-mathml="AA[" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">AA[AA[ 的数量。

[backcolor=rgba(255, 255, 255, 0.5)]总时间复杂度 <span class="MathJax" id="MathJax-Element-54-Frame" tabindex="0" data-mathml="O(|S|log&#x2061;|S|)" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">O(|S|log|S|)O(|S|log&#8289;|S|)，空间复杂度 <span class="MathJax" id="MathJax-Element-55-Frame" tabindex="0" data-mathml="O(|S|)" role="presentation" style="display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">O(|S|)O(|S|)。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define N 2000010#define db double#define alp 0.72#define MAXD 1e16using namespace std;char str[N],s[N];db v[N];int ch[N][2],siz[N];int swp[N],stot,rt;void upd(int u){siz=siz[ch[0]]+siz[ch[1]]+1;}void dfs(int u){        if(!u) return;        dfs(ch[0]),swp[++stot]=u;dfs(ch[1]);        ch[0]=ch[1]=0;}void build(int &u,int l,int r,db lf=0,db rf=MAXD){        if(l>r) return;        int mid=(l+r)>>1;db mf=(lf+rf)/2;        u=swp[mid];        v=mf;        build(ch[0],l,mid-1,lf,mf),build(ch[1],mid+1,r,mf,rf);        upd(u);}void reb(int &u,db lf,db rf){        if(max(siz[ch[0]],siz[ch[1]])<siz*alp) return;        stot=0;dfs(u);        build(u,1,stot,lf,rf);}int cmp(int x,int y){return s[x]==s[y]?v[x-1]<v[y-1]:s[x]<s[y];}void insert(int &u,int k,db lf=0,db rf=MAXD){        if(!u){siz[u=k]=1;v=(lf+rf)/2;ch[0]=ch[1]=0;return;}        if(cmp(k,u)) insert(ch[0],k,lf,v);        else insert(ch[1],k,v,rf);        upd(u),reb(u,lf,rf);}void erase(int &u,int k){        if(u==k)        {                if(!ch[0] || !ch[1]){u=ch[0]|ch[1];return;}                int p=ch[0],las=u;                for(;ch[p][1];las=p,p=ch[p][1]) siz[p]--;                if(las==u) ch[p][1]=ch[1];                else ch[p][0]=ch[0],ch[p][1]=ch[1],ch[las][1]=0;                u=p;                upd(u);                return;        }        if(cmp(k,u)) erase(ch[0],k);        else erase(ch[1],k);        upd(u);}bool cmp_s(int u){for(int i=1;str;i++,u=u-!!u) if(str!=s) return str<s;return false;}int answer(int u){        if(!u) return 0;        if(cmp_s(u)) return answer(ch[0]);        else return answer(ch[1])+siz[ch[0]]+1;}void get_c(char s[],int mask){        int len=strlen(s);        for(int i=0;i<len;i++)        {                mask=(mask*131+i)%len;                char t=s;                s=s[mask];                s[mask]=t;        }}char opt[7];int main(){        int n,m,k,las=0;        scanf("%d%s",&m,s+1);n=strlen(s+1);        for(int i=1;i<=n;i++)        insert(rt,i);        for(int i=1;i<=m;i++)        {                scanf("%s",opt);                if(opt[0]=='D'){scanf("%d",&k);while(k --> 0) erase(rt,n),n--;continue;}                scanf("%s",str+1);                get_c(str+1,las);                int l=strlen(str+1);                if(opt[0]=='A') for(int j=1;j<=l;j++) s[++n]=str[j],insert(rt,n);                else if(opt[0]=='Q')                {                        reverse(str+1,str+l+1);                        str[l+1]='Z'+1,str[l+2]='\0';                        int ans=answer(rt);                        str[l]--;                        ans-=answer(rt);                        printf("%d\n",ans);                        las^=ans;                }        }        return 0;}//压行？不存在的。有相同爱好的可以进来一起讨论哦：企鹅群号：1046795523学习视频资料：http://www.makeru.com.cn/live/1392_1164.html?s=143793

三叶草

看着头晕