后缀数组学习笔记

xtx1092515503 · 2020-07-25 19:31:53 · 个人记录

upd：已将SA和SAM分开，现在这里是单独的SA学习笔记。

后缀数组（SA），是一种非常强大非常令人迷惑的数据结构。这里是一份关于它的学习笔记。

这里不会讲解它的基础芝士因为那玩意写起来太烦人了，而是着重于它的应用，类似于一份题单。

一些定义：

这个柿子可以拆成两部分，即

前一半很好求，就是\dfrac{n(n+1)(n-1)}{2}，关键是后一半。

依据\text{LCP Lemma}，\operatorname{LCP}(i,j)=\min\limits_{i\leq j\leq k}ht_j，即区间最小值。

我们考虑求出ht数组。考虑每个ht_i会对多少个区间做出贡献（成为多少个区间的\min）。这是经典的单调栈问题，可以参见玉蟾宫。

复杂度O(n)，假如你使用DC3的话。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,x[500100],y[500100],sa[500100],ht[500100],rk[500100],buc[500100],stk[500100],tp,L[500100],R[500100];
char s[500100];
ll res;
bool mat(int a,int b,int k){
    if(y[a]!=y[b])return false;
    if((a+k<n)^(b+k<n))return false;
    if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
    return true;
}
void SA(){
    for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
    for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
    for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
    for(int k=1;k<n;k<<=1){
        int num=0;
        for(int i=n-k;i<n;i++)y[num++]=i;
        for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
        for(int i=0;i<=m;i++)buc[i]=0;
        for(int i=0;i<n;i++)buc[x[y[i]]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i],y[i]=0;
        swap(x,y);
        x[sa[0]]=num=0;
        for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
        m=num;
    }
    for(int i=0;i<n;i++)rk[sa[i]]=i;
    for(int i=0,k=0;i<n;i++){
        if(!rk[i])continue;
        if(k)k--;
        int j=sa[rk[i]-1];
        while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
        ht[rk[i]]=k;
    }
}
int main(){
    scanf("%s",s),n=strlen(s),m='z';
    SA();
    res=1ll*n*(n+1)*(n-1)/2;
    for(int i=1;i<n;i++){
        while(tp&&ht[stk[tp]]>=ht[i])R[stk[tp--]]=i;
        L[i]=stk[tp],stk[++tp]=i;
    }
//  for(int i=0;i<n;i++)printf("%d ",rk[i]);puts("");
//  for(int i=0;i<n;i++)printf("%d ",ht[i]);puts("");
    while(tp)R[stk[tp--]]=n;
    for(int i=1;i<n;i++)res-=2ll*(i-L[i])*(R[i]-i)*ht[i];
    printf("%lld\n",res);
    return 0;
}

VII.[HAOI2016]找相同字符

第一道自己做出的SA题祭~~~

实际上和上一题没啥区别的说……

我们发现，这题实际上就是对于两个串中所有的后缀求\operatorname{LCP}之和（因为这两个后缀共有\operatorname{LCP}个前缀是相同的，即串中有这么多子串是相同的）。

老套路，俩串中间插个字符怼一起，求个ht数组。记录个前缀和，s1_i表示前i个字符有多少个来自串一，s2_i表示前i个字符有多少来自串二，然后仍然跑单调栈，算出所有来自不同串的后缀对数量，乘上ht求和即可。

关键代码：

for(int i=1;i<n;i++)res+=(1ll*(s1[i-1]-s1[L[i]-1])*(s2[R[i]-1]-s2[i-1])+1ll*(s2[i-1]-s2[L[i]-1])*(s1[R[i]-1]-s1[i-1]))*ht[i];

复杂度O(n)，假如你用DC3的话。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,p;
int x[400100],y[400100],sa[400100],ht[400100],rk[400100],buc[400100];
int stk[400100],tp,L[400100],R[400100];
int s1[400100],s2[400100];
char s[400100];
ll res;
bool mat(int a,int b,int k){
    if(y[a]!=y[b])return false;
    if((a+k<n)^(b+k<n))return false;
    if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
    return true;
}
void SA(){
    for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
    for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
    for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
    for(int k=1;k<n;k<<=1){
        int num=0;
        for(int i=n-k;i<n;i++)y[num++]=i;
        for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
        for(int i=0;i<=m;i++)buc[i]=0;
        for(int i=0;i<n;i++)buc[x[y[i]]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i],y[i]=0;
        swap(x,y);
        x[sa[0]]=num=0;
        for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
        m=num;
    }
    for(int i=0;i<n;i++)rk[sa[i]]=i;
    for(int i=0,k=0;i<n;i++){
        if(!rk[i])continue;
        if(k)k--;
        int j=sa[rk[i]-1];
        while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
        ht[rk[i]]=k;
    }
}
int main(){
    scanf("%s",s),p=strlen(s),s[p]=' ',scanf("%s",s+p+1),n=strlen(s),m='z';
//  printf("%s\n",s);
    SA();
    for(int i=1;i<n;i++)s1[i]=s1[i-1]+(sa[i]<p),s2[i]=s2[i-1]+(sa[i]>p);
//  for(int i=0;i<n;i++)printf("%d ",sa[i]);puts("");
//  for(int i=0;i<n;i++)printf("(%d,%d)",s1[i],s2[i]);puts("");
    for(int i=1;i<n;i++){
        while(tp&&ht[stk[tp]]>=ht[i])R[stk[tp--]]=i;
        L[i]=stk[tp],stk[++tp]=i;
    }
//  for(int i=0;i<n;i++)printf("%d ",rk[i]);puts("");
    while(tp)R[stk[tp--]]=n;
//  for(int i=1;i<n;i++)printf("%d:(%d,%d):%d\n",i,L[i],R[i],ht[i]);
    for(int i=1;i<n;i++)res+=(1ll*(s1[i-1]-s1[L[i]-1])*(s2[R[i]-1]-s2[i-1])+1ll*(s2[i-1]-s2[L[i]-1])*(s1[R[i]-1]-s1[i-1]))*ht[i];
    printf("%lld\n",res);
    return 0;
}

VIII.[SDOI2008]Sandy的卡片

……有什么意义吗……

差个分，然后就是IV.[POI2000]公共串的内容了，套个单调队列，O(n)解决，假如你用DC3的话。

代码：

#include<bits/stdc++.h>
using namespace std;
int all,n,m,s[200100],id[200100],x[200100],y[200100],buc[200100],sa[200100],ht[200100],rk[200100],res,occ[200100];
void SA(){
    for(int i=1;i<=n;i++)buc[x[i]=s[i]]++;
    for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
    for(int i=n;i;i--)sa[buc[x[i]]--]=i;
    for(int k=1;k<=n;k<<=1){
        int num=0;
        for(int i=n-k+1;i<=n;i++)y[++num]=i;
        for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
        for(int i=0;i<=m;i++)buc[i]=0;
        for(int i=1;i<=n;i++)buc[x[y[i]]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n;i;i--)sa[buc[x[y[i]]]--]=y[i],y[i]=0;
        swap(x,y);
        x[sa[1]]=num=1;
        for(int i=2;i<=n;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
        m=num;
    }
    for(int i=1;i<=n;i++)rk[sa[i]]=i;
    for(int i=1,k=0;i<=n;i++){
        if(rk[i]==1)continue;
        if(k)k--;
        int j=sa[rk[i]-1];
        while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])k++;
        ht[rk[i]]=k;
    }
}
deque<int>q;
int main(){
    scanf("%d",&all);
    for(int i=1,x;i<=all;i++){
        scanf("%d",&m),m--;
        for(int j=0;j<=m;j++)scanf("%d",&s[n+j]);
        for(int j=m;j;j--)s[n+j]-=s[n+j-1],s[n+j]+=10000,id[n+j]=i;
        s[n]=i-1,n+=m,n++;
    }
    n--,m=20000;
//  for(int i=1;i<=n;i++)printf("%d ",s[i]);puts("");
    SA();
//  for(int i=1;i<=n;i++)printf("%d ",rk[i]);puts("");
//  for(int i=1;i<=n;i++)printf("%d ",id[i]);puts("");
    for(int i=1,j=1,k=0;i<=n;i++){
        while(j<=n&&k<all){
            if(id[sa[j]])k+=!occ[id[sa[j]]]++;
            while(!q.empty()&&ht[q.back()]>=ht[j])q.pop_back();
            q.push_back(j++);
        }
        while(!q.empty()&&q.front()<=i)q.pop_front();
        if(k==all)res=max(res,ht[q.front()]);
        if(id[sa[i]])k-=!--occ[id[sa[i]]];
    }
    printf("%d\n",res+1);
    return 0;
}

IX.[JSOI2007]字符加密

这题的思路非常简单——断环复制成链，然后直接后缀排序一下即可。

为什么呢？

我们考虑两条后缀。假如它们在前n位中有所不同，显然它们之间的相对顺序不会有问题；

否则，假如它们前n位全都相同，则因为反正最后输出的就是最后一个字符，所以相对顺序没有影响，直接按照更往后的东西决定顺序也没有问题。

总复杂度O(n)，假如DC3。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,buc[400100],x[400100],y[400100],sa[400100];
char s[400100];
bool mat(int a,int b,int k){
    if(y[a]!=y[b])return false;
    if((a+k<n)^(b+k<n))return false;
    if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
    return true;
}
void SA(){
    for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
    for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
    for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
    for(int k=1;k<n;k<<=1){
        int num=0;
        for(int i=n-k;i<n;i++)y[num++]=i;
        for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
        for(int i=0;i<=m;i++)buc[i]=0;
        for(int i=0;i<n;i++)buc[x[y[i]]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i],y[i]=0;
        swap(x,y);
        x[sa[0]]=num=0;
        for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
        m=num;
    }
}
int main(){
    scanf("%s",s),n=strlen(s);
    for(int i=0;i<n;i++)s[i+n]=s[i];
    n<<=1,m='z';
//  printf("%s:%d,%d\n",s,n,m);
    SA();
    n>>=1;
    for(int i=0;i<(n<<1);i++)if(sa[i]<n)printf("%c",s[sa[i]+n-1]);
    return 0;
}

X.[SCOI2012]喵星球上的点名

我居然做出了这题……难以置信！

首先，思路很明显是把所有串全怼一起（包括名字和询问串），加上分隔符，然后跑一遍后缀数组。

我们仍然可以用单调栈求出关于每个询问串与它相同的区间。即，如果以询问串为前缀的那个后缀的rank是p的话，它的合法区间[L,R]应该满足\forall L<i\leq R,ht_i\geq ht_p。注意这里是\geq而非>，因此应该特别注意处理=的部分。

这里放一下求出全部[L,R)的代码（注意这里数组中的[L,R)实际上是左闭右开的，而我们最终要求的[L,R]是左闭右闭的，所以接下来用的时候R要减去1）：

for(int i=1;i<n;i++){
    while(tp&&ht[stk[tp]]>ht[i])R[stk[tp--]]=i;
    if(ht[stk[tp]]==ht[i])L[i]=L[stk[tp]];
    else L[i]=stk[tp];
    stk[++tp]=i;
}
while(tp)R[stk[tp--]]=n;

求出所有合法的[L,R]后，我们可以考虑那两个询问了。

首先，对于第一问，发现它就是求区间[L,R]内部所有出现过的姓名串的数量。这不就是[SDOI2009]HH的项链吗？树状数组即可。当然你要真想写莫队也没人拦得住你。

然后，关于第二问，它的意义实际上是将区间[L,R]内部所有出现过的姓名串的计数器增加1。如果关于询问串下手我们没有办法，但是我们可以关于姓名串下手呀！

我们设一个下标i，它所代表的姓名串为代码中的id\big[sa[i]\big]，我们这里设一个c_i代表它。我们再设它之前上一个出现的该姓名串的下标为LAS_i（如果之前没有出现任何这个姓名串的下标，LAS_i=-1）。则显然，所有满足i\in[L,R]且LAS_i<L的区间[L,R]都可以对c_i有贡献。这是什么？二维数点问题呀！

于是我们愉快地排个序就能用线段树求出答案。

复杂度O(n\log n)。

代码：

#include<bits/stdc++.h>
using namespace std;
int S,T,cnt,id[400100],tms[400100],ans[400100],stt[400100],P,Q,len[400100];
//-------------------Suffix Array Below--------------------
int stk[400100],tp,L[400100],R[400100];
namespace Suffix_Array{
    int x[400100],y[400100],sa[400100],ht[400100],rk[400100],buc[400100],s[400100],n,m;
    bool mat(int a,int b,int k){
        if(y[a]!=y[b])return false;
        if((a+k<n)^(b+k<n))return false;
        if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
        return true;
    }
    void SA(){
        for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
        for(int k=1;k<n;k<<=1){
            int num=0;
            for(int i=n-k;i<n;i++)y[num++]=i;
            for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
            for(int i=0;i<=m;i++)buc[i]=0;
            for(int i=0;i<n;i++)buc[x[y[i]]]++;
            for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
            for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i],y[i]=0;
            swap(x,y);
            x[sa[0]]=num=0;
            for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
            m=num;
        }
        for(int i=0;i<n;i++)rk[sa[i]]=i;
        for(int i=0,k=0;i<n;i++){
            if(!rk[i])continue;
            if(k)k--;
            int j=sa[rk[i]-1];
            while(j+k<n&&i+k<n&&s[j+k]==s[i+k])k++;
            ht[rk[i]]=k;
        }
    }   
}
using namespace Suffix_Array;
//------------------Suffix Array Above---------------------
int las[400100],LAS[400100];
//------------------Ask the Queries Below------------------
struct Query{
    int l,r,id;
    Query(int a=0,int b=0,int c=0){l=a,r=b,id=c;}
}q[400100];
bool cmp1(Query &u,Query &v){
    return u.r<v.r;
}
int t[400100];
void add(int x,int y){
    x++;
    while(x<=n)t[x]+=y,x+=x&-x;
}
int sum(int x){
    x++;
    int ret=0;
    while(x)ret+=t[x],x-=x&-x;
    return ret;
}
//------------------Ask the Queries Above------------------
//-----------------Calculate the Times Below---------------
pair<int,int>p[400100];
bool cmp(pair<int,int>&u,pair<int,int>&v){//first:place second:last
    return u.second>v.second;
}
bool cmp2(Query &u,Query &v){
    return u.l>v.l;
}
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
int tag[1600100];
void pushdown(int x){tag[lson]+=tag[x],tag[rson]+=tag[x],tag[x]=0;}
void modify(int x,int l,int r,int L,int R){
    if(l>R||r<L)return;
    if(L<=l&&r<=R){tag[x]++;return;}
    pushdown(x),modify(lson,l,mid,L,R),modify(rson,mid+1,r,L,R);
}
int query(int x,int l,int r,int P){
    if(l>P||r<P)return 0;
    if(l==r)return tag[x];
    pushdown(x);
    return query(lson,l,mid,P)+query(rson,mid+1,r,P);
}
#undef lson
#undef rson
#undef mid
//----------------------Calculate the Times Above----------
int main(){
    scanf("%d%d",&S,&T),cnt=10000;
    for(int i=1;i<=S;i++){
        scanf("%d",&m);
        for(int j=0;j<m;j++)scanf("%d",&s[n+j]),id[n+j]=i;
        n+=m;
        s[n++]=++cnt;
        scanf("%d",&m);
        for(int j=0;j<m;j++)scanf("%d",&s[n+j]),id[n+j]=i;
        n+=m;
        s[n++]=++cnt;
    }
    for(int i=1;i<=T;i++){
        scanf("%d",&m),stt[i]=n;
        len[i]=m;
        for(int j=0;j<m;j++)scanf("%d",&s[n+j]),id[n+j]=S+i;
        n+=m;
        s[n++]=++cnt;
    }
    m=cnt;
    SA();
    for(int i=1;i<n;i++){
        while(tp&&ht[stk[tp]]>ht[i])R[stk[tp--]]=i;
        if(ht[stk[tp]]==ht[i])L[i]=L[stk[tp]];
        else L[i]=stk[tp];
        stk[++tp]=i;
    }
    while(tp)R[stk[tp--]]=n;
    for(int i=1;i<=T;i++)if(ht[rk[stt[i]]]==len[i])q[++Q]=Query(L[rk[stt[i]]],R[rk[stt[i]]]-1,i);
//  for(int i=0;i<n;i++)printf("%2d::S:%5d id:%d rk:%2d sa:%2d ht:%d\n",i,s[i],id[i],rk[i],sa[i],ht[i]);
//  for(int i=1;i<=T;i++)printf("%d %d\n",q[i].l,q[i].r);
    sort(q+1,q+Q+1,cmp1),memset(las,-1,sizeof(las));
    for(int i=1,j=0;i<=Q;i++){
        for(;j<=q[i].r;j++){
            if(id[sa[j]]>S||!id[sa[j]])continue;
            LAS[j]=las[id[sa[j]]],las[id[sa[j]]]=j;
            if(LAS[j]!=-1)add(LAS[j],-1);
            add(j,1);
            p[++P]=make_pair(j,LAS[j]);
        }
        ans[q[i].id]=sum(q[i].r)-sum(q[i].l-1);
    }
    for(int i=1;i<=T;i++)printf("%d\n",ans[i]);
    sort(q+1,q+Q+1,cmp2),sort(p+1,p+P+1,cmp);
    for(int i=1,j=1;i<=P;i++){
        while(j<=Q&&p[i].second<q[j].l)modify(1,0,n-1,q[j].l,q[j].r),j++;
        tms[id[sa[p[i].first]]]+=query(1,0,n-1,p[i].first);
    }
    for(int i=1;i<=S;i++)printf("%d ",tms[i]);
    return 0;
}

XI.[APIO2014]回文串

题解

XII.[TJOI2015]弦论

题解

XIII.[BJWC2010]外星联络

和上题一样，没啥好说的，直接建出笛卡尔树即可。

代码：

#include<bits/stdc++.h>
using namespace std;
int stk[500100],tp,L[500100],R[500100],id,pt;
namespace Suffix_Array{
    const int N=500100;
    int x[N],y[N],sa[N],ht[N],rk[N],buc[N],n,m;
    char s[N];
    bool mat(int a,int b,int k){
        if(y[a]!=y[b])return false;
        if((a+k<n)^(b+k<n))return false;
        if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
        return true;
    }
    void SA(){
        for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
        for(int k=1;k<n;k<<=1){
            int num=0;
            for(int i=n-k;i<n;i++)y[num++]=i;
            for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
            for(int i=0;i<=m;i++)buc[i]=0;
            for(int i=0;i<n;i++)buc[x[y[i]]]++;
            for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
            for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i],y[i]=0;
            swap(x,y);
            x[sa[0]]=num=0;
            for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
            m=num;
        }
        for(int i=0;i<n;i++)rk[sa[i]]=i;
        for(int i=0,k=0;i<n;i++){
            if(!rk[i])continue;
            if(k)k--;
            int j=sa[rk[i]-1];
            while(j+k<n&&i+k<n&&s[j+k]==s[i+k])k++;
            ht[rk[i]]=k;
        }
    }   
}
using namespace Suffix_Array;
int mn[500100][20],LG[500100];
int MIN(int i,int j){
    return ht[i]<=ht[j]?i:j;
}
int RMQ(int l,int r){
    int k=LG[r-l+1];
    return MIN(mn[l][k],mn[r-(1<<k)+1][k]);
}
void solve(int l,int r,int las){
//  printf("%d %d %d\n",l,r,las);
    if(l>r)return;
    int mp=RMQ(l,r);
    for(int j=las;j<ht[mp];j++)printf("%d\n",r-l+2);
    solve(l,mp-1,ht[mp]),solve(mp+1,r,ht[mp]);
}
int main(){
    scanf("%d%s",&n,s),m='1';
    SA();
    for(int i=2;i<n;i++)LG[i]=LG[i>>1]+1;
    for(int i=1;i<n;i++)mn[i][0]=i;
    for(int j=1;j<=LG[n-1];j++)for(int i=1;i+(1<<j)-1<n;i++)mn[i][j]=MIN(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
    solve(1,n-1,0);
    return 0;
}
/*
aabbababb
1 12
*/

XIV.[SDOI2016]生成魔咒

动态SA？这怎么办？

我们考虑往每个后缀后面全都加入一个数。很明显，如果这样搞的话，你必须每加入一个数后都要重新后缀排序，不太可能完成。

这时，我们发现，如果这不是加入一个数，而是加入一整条后缀，那就会轻松很多，一个平衡树就能搞定。

思考后会发现，如果我们将整个串翻转，则原本是加入一个数，现在则变成了加入一条后缀！并且，翻转对答案并无影响——毕竟本质不同子串数无论正着来还是反着来都是一样的。

当你加入一条后缀时，所有新增加的子串数量，就等于n-i-\max\limits_{j>i}\{\operatorname{LCP}(i,j)\}。

应用\text{LCP Lemma}，我们知道\operatorname{LCP}(i,j)=\min\limits_{rk_i<k\leq rk_j}ht_k

则显然，只有rk_i左右侧的rk_j才会是最大值。于是我们就可以用一个std::set来维护所有的rk_j，记为\mathbb{S}。则每加入一个数，就在\mathbb{S}中二分到前后的rk_j然后求\operatorname{LCP}即可。

复杂度O(n\log n)。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace Suffix_Array{
    const int N=100100;
    int x[N],y[N],sa[N],ht[N],rk[N],buc[N],n,m,s[N];
    bool mat(int a,int b,int k){
        if(y[a]!=y[b])return false;
        if((a+k<n)^(b+k<n))return false;
        if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
        return true;
    }
    void SA(){
        for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
        for(int k=1;k<n;k<<=1){
            int num=0;
            for(int i=n-k;i<n;i++)y[num++]=i;
            for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
            for(int i=0;i<=m;i++)buc[i]=0;
            for(int i=0;i<n;i++)buc[x[y[i]]]++;
            for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
            for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i],y[i]=0;
            swap(x,y);
            x[sa[0]]=num=0;
            for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
            m=num;
        }
        for(int i=0;i<n;i++)rk[sa[i]]=i;
        for(int i=0,k=0;i<n;i++){
            if(!rk[i])continue;
            if(k)k--;
            int j=sa[rk[i]-1];
            while(j+k<n&&i+k<n&&s[j+k]==s[i+k])k++;
            ht[rk[i]]=k;
        }
    }   
}
using namespace Suffix_Array;
int mn[100100][20],LG[100100];
int LCP(int l,int r){//get the LCP of suffix l and r;
    l++;
    int k=LG[r-l+1];
    return min(mn[l][k],mn[r-(1<<k)+1][k]);
}
vector<int>v;
set<int>st;
ll res;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&s[i]),v.push_back(s[i]);
    sort(v.begin(),v.end()),v.resize(m=unique(v.begin(),v.end())-v.begin());
    for(int i=0;i<n;i++)s[i]=lower_bound(v.begin(),v.end(),s[i])-v.begin()+1;
    reverse(s,s+n);
    SA();
    for(int i=2;i<n;i++)LG[i]=LG[i>>1]+1;
    for(int i=1;i<n;i++)mn[i][0]=ht[i];
    for(int j=1;j<=LG[n-1];j++)for(int i=1;i+(1<<j)-1<n;i++)mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
    for(int i=n-1;i>=0;i--){
        int sm=0;
        auto it=st.upper_bound(rk[i]);
        if(it!=st.end())sm=max(sm,LCP(rk[i],*it));
        if(it!=st.begin())it--,sm=max(sm,LCP(*it,rk[i]));
        st.insert(rk[i]);
        res+=n-i-sm;
        printf("%lld\n",res);
    }
    return 0;
} 

XV.Annihilate

我当年为什么会手贱开这卡常大毒瘤题呀

思路1. 用vector存下每个字符串在后缀排序后的下标，然后每次枚举两个串，用一个vector里面的数在另一个里面two-pointers找到它两侧的数，然后用ST表求LCP。

时间复杂度O\Big(\sum|S|(\log\sum|S|+n^2)\Big)，空间复杂度O(n\log n)，光荣MLE。

代码：

#include<bits/stdc++.h>
using namespace std;
int all,id[1001000],res[100][100];
namespace Suffix_Array{
    const int N=1001000;
    int x[N],y[N],sa[N],ht[N],rk[N],buc[N],n,m;
    char s[N];
    bool mat(int a,int b,int k){
        if(y[a]!=y[b])return false;
        if((a+k<n)^(b+k<n))return false;
        if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
        return true;
    }
    void SA(){
        for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
        for(int k=1;k<n;k<<=1){
            int num=0;
            for(int i=n-k;i<n;i++)y[num++]=i;
            for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
            for(int i=0;i<=m;i++)buc[i]=0;
            for(int i=0;i<n;i++)buc[x[y[i]]]++;
            for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
            for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i],y[i]=0;
            swap(x,y);
            x[sa[0]]=num=0;
            for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
            m=num;
        }
        for(int i=0;i<n;i++)rk[sa[i]]=i;
        for(int i=0,k=0;i<n;i++){
            if(!rk[i])continue;
            if(k)k--;
            int j=sa[rk[i]-1];
            while(j+k<n&&i+k<n&&s[j+k]==s[i+k])k++;
            ht[rk[i]]=k;
        }
    }   
}
using namespace Suffix_Array;
vector<int>v[60];
int mn[1001000][20],LG[1001000];
int LCP(int l,int r){//get the LCP of suffix l and r;
    l++;
    int k=LG[r-l+1];
    return min(mn[l][k],mn[r-(1<<k)+1][k]);
}
int main(){
    scanf("%d",&all);
    for(int i=1;i<=all;i++){
        scanf("%s",s+n);
        m=strlen(s+n);
        for(int j=n;j<n+m;j++)id[j]=i;
        n+=m;
        s[n++]=i;
    }
    m='z';
    SA();
    for(int i=2;i<n;i++)LG[i]=LG[i>>1]+1;
    for(int i=1;i<n;i++)mn[i][0]=ht[i];
    for(int j=1;j<=LG[n-1];j++)for(int i=1;i+(1<<j)-1<n;i++)mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
    for(int i=0;i<n;i++)if(id[sa[i]])v[id[sa[i]]].push_back(i);
    for(int i=1;i<=all;i++)for(int j=i+1;j<=all;j++){
        for(int a=0,b=0;a<v[i].size();a++){
            while(b<v[j].size()&&v[i][a]>v[j][b])b++;
            if(b<v[j].size())res[i][j]=max(res[i][j],LCP(v[i][a],v[j][b]));
            if(b)res[i][j]=max(res[i][j],LCP(v[j][b-1],v[i][a]));
        }
    }
    for(int i=1;i<=all;i++){for(int j=1;j<=all;j++)if(i!=j)printf("%d ",res[min(i,j)][max(i,j)]);puts("");}
    return 0;
} 

思路2. 用单调队列求LCP

大体思路和上题一致，只不过换用单调队列求LCP。

时间复杂度O\Big(\sum|S|(\log\sum|S|+n^2)\Big)，光荣TLE。

代码：

#include<bits/stdc++.h>
using namespace std;
int all,id[1001000],res[100][100];
namespace Suffix_Array{
    const int N=1001000;
    int x[N],y[N],sa[N],ht[N],rk[N],buc[N],n,m;
    char s[N];
    bool mat(int a,int b,int k){
        if(y[a]!=y[b])return false;
        if((a+k<n)^(b+k<n))return false;
        if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
        return true;
    }
    void SA(){
        for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
        for(int k=1;k<n;k<<=1){
            int num=0;
            for(int i=n-k;i<n;i++)y[num++]=i;
            for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
            for(int i=0;i<=m;i++)buc[i]=0;
            for(int i=0;i<n;i++)buc[x[y[i]]]++;
            for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
            for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i],y[i]=0;
            swap(x,y);
            x[sa[0]]=num=0;
            for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
            m=num;
        }
        for(int i=0;i<n;i++)rk[sa[i]]=i;
        for(int i=0,k=0;i<n;i++){
            if(!rk[i])continue;
            if(k)k--;
            int j=sa[rk[i]-1];
            while(j+k<n&&i+k<n&&s[j+k]==s[i+k])k++;
            ht[rk[i]]=k;
        }
    }   
}
using namespace Suffix_Array;
vector<int>v[60];
int main(){
    scanf("%d",&all);
    for(int i=1;i<=all;i++){
        scanf("%s",s+n);
        m=strlen(s+n);
        for(int j=n;j<n+m;j++)id[j]=i;
        n+=m;
        s[n++]=i;
    }
    m='z';
    SA();
    for(int i=1;i<=all;i++)v[i].push_back(i);
    for(int i=0;i<n;i++)if(id[sa[i]])v[id[sa[i]]].push_back(i);
    for(int i=1;i<=all;i++)for(int j=i+1;j<=all;j++){
        deque<int>p,q;
        for(int a=1,b=0;a<v[i].size();a++){
            for(int k=v[i][a-1]+1;k<=v[i][a];k++){
                while(!p.empty()&&ht[p.back()]>=ht[k])p.pop_back();
                p.push_back(k);
            }
            while(b<v[j].size()&&v[i][a]>v[j][b]){
                while(!p.empty()&&p.front()<=v[j][b])p.pop_front();
                b++;
                if(b==v[j].size())break;
                for(int k=v[j][b-1]+1;k<=v[j][b];k++){
                    while(!q.empty()&&ht[q.back()]>=ht[k])q.pop_back();
                    q.push_back(k);
                }
            }
            while(!q.empty()&&q.front()<=v[i][a])q.pop_front();
            if(!p.empty())res[i][j]=max(res[i][j],ht[p.front()]);
            if(!q.empty())res[i][j]=max(res[i][j],ht[q.front()]);
        }
    }
    for(int i=1;i<=all;i++){for(int j=1;j<=all;j++)if(i!=j)printf("%d ",res[min(i,j)][max(i,j)]);puts("");}
    return 0;
} 

思路3.正解

我们设一个las_i表示当前位置到上一个来自i串的后缀的区间中的\min ht_x。到了每一个位置O(n)地遍历las数组更新并计算答案。复杂度O\Big(\sum|S|\log(\sum|S|+n)\Big)，可以通过。

但是这题卡常强烈吐槽！

代码（开O2通过）：

#include<bits/stdc++.h>
using namespace std;
int all,id[1010000],res[100][100],las[100];
namespace Suffix_Array{
    const int N=1010000;
    int x[N],y[N],sa[N],ht[N],rk[N],buc[N],n,m,s[N];
    void SA(){
        for(int i=1;i<=n;i++)buc[x[i]=s[i]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n;i;i--)sa[buc[x[i]]--]=i;
        for(int k=1;k<=n;k<<=1){
            int num=0;
            for(int i=n-k+1;i<=n;i++)y[++num]=i;
            for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
            for(int i=0;i<=m;i++)buc[i]=0;
            for(int i=1;i<=n;i++)buc[x[y[i]]]++;
            for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
            for(int i=n;i;i--)sa[buc[x[y[i]]]--]=y[i],y[i]=0;
            swap(x,y);
            x[sa[1]]=num=1;
            for(int i=2;i<=n;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
            if(num>=n)break;
            m=num;
        }
        for(int i=1;i<=n;i++)rk[sa[i]]=i;
        for(int i=1,k=0;i<=n;i++){
            if(rk[i]==1)continue;
            if(k)k--;
            int j=sa[rk[i]-1];
            while(j+k<=n&&i+k<=n&&s[j+k]==s[i+k])k++;
            ht[rk[i]]=k;
        }
    }   
}
using namespace Suffix_Array;
char str[1001000];
int main(){
    scanf("%d",&all);
    for(int i=1;i<=all;i++){
        scanf("%s",str);
        m=strlen(str);
        for(int j=0;j<m;j++)n++,s[n]=str[j]-'a'+1,id[n]=i;
        s[++n]=i+26;
    }
    m=all+26;
    SA();
//  for(int i=1;i<=n;i++)printf("%d ",s[i]);puts("");
//  for(int i=1;i<=n;i++)printf("%d ",rk[i]);puts("");
    for(int i=2;i<=n;i++){
        for(int j=1;j<=all;j++)las[j]=min(las[j],ht[i]);
        las[id[sa[i-1]]]=ht[i];
        for(int j=1;j<=all;j++)res[j][id[sa[i]]]=max(res[j][id[sa[i]]],las[j]);
    }
    for(int i=1;i<=all;i++){for(int j=1;j<=all;j++)if(i!=j)printf("%d ",max(res[i][j],res[j][i]));puts("");}
    return 0;
} 

XVI.[NOI2015]品酒大会

我居然能自己AC NOI的原题，后缀数组果然简单

首先当然是轻松建出SA。

我们考虑借鉴XII.[TJOI2015]弦论的思想，建出笛卡尔树。则对于当前的ht长度，它出现在了(l,r)区间里的每一个后缀里，共计\dfrac{(r-l+2)(r-l+1)}{2}次。同时，这份贡献会对(ht_{(l,r)},ht_{fa})区间中的每一个”r相似“全部有这么多的贡献，因此直接差个分即可。同时，这个区间内部任意两个a_{sa_i}\times a_{sa_j}的\max，要么来自于（\text{最大}\times\text{次大}），要么来自于（\text{最小}\times\text{次小}），用线段树维护即可。最后，对差分数组做后缀和，对\max数组求后缀\max即可。

复杂度O(n\log n)，TLE。

代码：

#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[300100];
int x[300100],y[300100],sa[300100],ht[300100],rk[300100],buc[300100];
char s[300100];
bool mat(int a,int b,int k){
    if(y[a]!=y[b])return false;
    if((a+k<n)^(b+k<n))return false;
    if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
    return true;
}
void SA(){
    for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
    for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
    for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
    for(int k=1;k<n;k<<=1){
        int num=0;
        for(int i=n-k;i<n;i++)y[num++]=i;
        for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
        for(int i=0;i<=m;i++)buc[i]=0;
        for(int i=0;i<n;i++)buc[x[y[i]]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
        swap(x,y);
        x[sa[0]]=num=0;
        for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
        m=num;
    }
    for(int i=0;i<n;i++)rk[sa[i]]=i;
    for(int i=0,k=0;i<n;i++){
        if(!rk[i])continue;
        if(k)k--;
        int j=sa[rk[i]-1];
        while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
        ht[rk[i]]=k;
    }
}
int LG[300100],mn[300100][20];
ll cnt[300100],mx[300100];
int MIN(int x,int y){return ht[x]<=ht[y]?x:y;}
int RMQ(int l,int r){
    int k=LG[r-l+1];
    return MIN(mn[l][k],mn[r-(1<<k)+1][k]);
}
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
struct SegTree{
    int mx1,mx2,mn1,mn2;
    SegTree(){mx1=mx2=0x80808080,mn1=mn2=0x3f3f3f3f;}
    SegTree(int x){mx1=mn1=x,mx2=0x80808080,mn2=0x3f3f3f3f;}
    friend SegTree operator +(const SegTree &x,const SegTree &y){
        SegTree z;
        vector<int>v;
        v={x.mx1,x.mx2,y.mx1,y.mx2};
        sort(v.begin(),v.end());
        z.mx1=v[3],z.mx2=v[2];
        v={x.mn1,x.mn2,y.mn1,y.mn2};
        sort(v.begin(),v.end());
        z.mn1=v[0],z.mn2=v[1];
        return z;
    }
    ll calc(){
        ll ret=0x8080808080808080;
        if(mn1!=0x3f3f3f3f&&mn2!=0x3f3f3f3f)ret=max(ret,1ll*mn1*mn2);
        if(mx1!=0x80808080&&mx2!=0x80808080)ret=max(ret,1ll*mx1*mx2);
        return ret;
    }
}seg[1200100];
void build(int x,int l,int r){
    if(l==r){seg[x]=SegTree(a[sa[l]]);return;}
    build(lson,l,mid),build(rson,mid+1,r),seg[x]=seg[lson]+seg[rson]; 
}
SegTree query(int x,int l,int r,int L,int R){
    if(l>R||r<L)return SegTree();
    if(L<=l&&r<=R)return seg[x];
    return query(lson,l,mid,L,R)+query(rson,mid+1,r,L,R);
}
void solve(int l,int r,int las){
    if(l>r)return;
    int mp=RMQ(l,r),len=r-l+2;
    cnt[ht[mp]]+=1ll*len*(len-1)/2,mx[ht[mp]]=max(mx[ht[mp]],query(1,0,n-1,l-1,r).calc());
    cnt[las]-=1ll*len*(len-1)/2;
    solve(l,mp-1,ht[mp]),solve(mp+1,r,ht[mp]);
}
int main(){
    scanf("%d%s",&n,s),m='z',memset(mx,0x80,sizeof(mx));
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    SA();
    for(int i=2;i<n;i++)LG[i]=LG[i>>1]+1;
    for(int i=1;i<n;i++)mn[i][0]=i;
    for(int j=1;j<=LG[n-1];j++)for(int i=1;i+(1<<j)-1<n;i++)mn[i][j]=MIN(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
    build(1,0,n-1),solve(1,n-1,-1);
    for(int i=n-1;i>=0;i--)cnt[i]+=cnt[i+1],mx[i]=max(mx[i],mx[i+1]);
    for(int i=0;i<n;i++)printf("%lld %lld\n",cnt[i],cnt[i]==0ll?0ll:mx[i]);
    return 0;
}

既然如此，我们只能考虑O(n)地建笛卡尔树并O(n)维护最大次大值。

在经历多次失败后，我找出了O(n)建树的方法：

for(int i=1;i<n;i++){
    while(tp&&ht[stk[tp]]>ht[i])R[stk[tp]]=i,lson[i]=stk[tp],tp--;
    L[i]=stk[tp],rson[stk[tp]]=i,stk[++tp]=i;
}
while(tp)R[stk[tp--]]=n;
rt=stk[1];
solve(rt,-1);

但是怎样O(n)维护呢？

又经过实验后，我发现这个最大次大值可以通过两个儿子的值合并算出来。如果某个儿子不存在的话，就要把对应的端点贡献算入。

这里是O(n)的solve函数：

void solve(int x,int las){
    int len=R[x]-L[x];
    cnt[ht[x]]+=1ll*len*(len-1)/2;
    cnt[las]-=1ll*len*(len-1)/2;
    if(lson[x])solve(lson[x],ht[x]),dat[x]+=dat[lson[x]];
    else dat[x]+=Data(a[sa[L[x]]]);
    if(rson[x])solve(rson[x],ht[x]),dat[x]+=dat[rson[x]];
    else dat[x]+=Data(a[sa[R[x]-1]]);
    mx[ht[x]]=max(mx[ht[x]],dat[x].calc());
}

其中dat[x]是一个类型为Data的struct，已经提前定义了加法，可以维护最大次大值。

总复杂度O(n\log n)，瓶颈为后缀排序，采用DC3算法即可优化到整体O(n)。但是不使用DC3仍然可以通过。

代码：

#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[300100];
int x[300100],y[300100],sa[300100],ht[300100],rk[300100],buc[300100];
char s[300100];
bool mat(int a,int b,int k){
    if(y[a]!=y[b])return false;
    if((a+k<n)^(b+k<n))return false;
    if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
    return true;
}
void SA(){
    for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
    for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
    for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
    for(int k=1;k<n;k<<=1){
        int num=0;
        for(int i=n-k;i<n;i++)y[num++]=i;
        for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
        for(int i=0;i<=m;i++)buc[i]=0;
        for(int i=0;i<n;i++)buc[x[y[i]]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
        swap(x,y);
        x[sa[0]]=num=0;
        for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
        m=num;
    }
    for(int i=0;i<n;i++)rk[sa[i]]=i;
    for(int i=0,k=0;i<n;i++){
        if(!rk[i])continue;
        if(k)k--;
        int j=sa[rk[i]-1];
        while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
        ht[rk[i]]=k;
    }
}
struct Data{
    int mx1,mx2,mn1,mn2;
    Data(){mx1=mx2=0x80808080,mn1=mn2=0x3f3f3f3f;}
    Data(int x){mx1=mn1=x,mx2=0x80808080,mn2=0x3f3f3f3f;}
    void Print()const{
        printf("%d %d %d %d\n",mx1,mx2,mn1,mn2);
    }
    void operator +=(const Data&x){
        if(x.mx1>=mx1)mx2=max(mx1,x.mx2),mx1=x.mx1;
        else mx2=max(mx2,x.mx1);
        if(x.mn1<=mn1)mn2=min(mn1,x.mn2),mn1=x.mn1;
        else mn2=min(mn2,x.mn1);
    }
    ll calc(){
        ll ret=0x8080808080808080;
        if(mn1!=0x3f3f3f3f&&mn2!=0x3f3f3f3f)ret=max(ret,1ll*mn1*mn2);
        if(mx1!=0x80808080&&mx2!=0x80808080)ret=max(ret,1ll*mx1*mx2);
        return ret;
    }
}dat[300100];
int stk[300100],tp,lson[300100],rson[300100],L[300100],R[300100],rt;
ll cnt[300100],mx[300100];
void solve(int x,int las){
    int len=R[x]-L[x];
    cnt[ht[x]]+=1ll*len*(len-1)/2;
    cnt[las]-=1ll*len*(len-1)/2;
    if(lson[x])solve(lson[x],ht[x]),dat[x]+=dat[lson[x]];
    else dat[x]+=Data(a[sa[L[x]]]);
    if(rson[x])solve(rson[x],ht[x]),dat[x]+=dat[rson[x]];
    else dat[x]+=Data(a[sa[R[x]-1]]);
//  printf("%d:(%d,%d):(%d,%d):%d\n",x,L[x],R[x]-1,lson[x],rson[x],ht[x]);
//  printf("%d:",x);dat[x].Print();
    mx[ht[x]]=max(mx[ht[x]],dat[x].calc());
}
int main(){
    scanf("%d%s",&n,s),m='z',memset(mx,0x80,sizeof(mx));
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    SA();
    for(int i=1;i<n;i++){
        while(tp&&ht[stk[tp]]>ht[i])R[stk[tp]]=i,lson[i]=stk[tp],tp--;
        L[i]=stk[tp],rson[stk[tp]]=i,stk[++tp]=i;
    }
    while(tp)R[stk[tp--]]=n;
//  for(int i=0;i<n;i++)printf("%d ",a[sa[i]]);puts("");
    rt=stk[1];
    solve(rt,-1);
    for(int i=n-1;i>=0;i--)cnt[i]+=cnt[i+1],mx[i]=max(mx[i],mx[i+1]);
    for(int i=0;i<n;i++)printf("%lld %lld\n",cnt[i],cnt[i]==0ll?0ll:mx[i]);
    return 0;
}

XVII.[USACO17DEC]Standing Out from the Herd P

一个naive的思路就是将所有串拼一起然后后缀排序，找出所有连续的来自同一个串的后缀。考虑结合I.不同子串个数思考，则如果该区间是[l,r]的话，它的贡献应该是\sum\limits_{l\leq i\leq r}len_{sa_i}-\sum\limits_{l\leq i\leq r+1}ht_i，其中len_{sa_i}是i位置的后缀的长度。注意因为这里要求在所有串中都没有出现过，所以ht_i的区间应是[l,r+1]，包括了前一个串和后一个串中的出现。

但是你会发现它有问题。假如你考虑极端情况，即l=r时，这是有重复部分的。

比如说下面举一个例子：

aaaaaa...

aaaab...

aaac...

这是后缀数组中三个连续的串。我们这时想要考虑中间那一个串在其他串中出现过的长度。显然，应该是len(aaaa)=4。

但是，两边的ht，一个是4，一个是3。你要两个都算的话，就算重复了。

因此我们对于上面的式子，还应该减去一个\operatorname{LCP}(l-1,r+1)，即正确的式子应该是\sum\limits_{l\leq i\leq r}len_{sa_i}-\sum\limits_{l\leq i\leq r+1}ht_i+\min\limits_{l\leq i\leq r+1}ht_i，这样才不会重复计算。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,all,id[300100],len[300100];
int x[300100],y[300100],sa[300100],ht[300100],rk[300100],buc[300100],s[300100];
ll res[300100];
char str[300100];
bool mat(int a,int b,int k){
    if(y[a]!=y[b])return false;
    if((a+k<n)^(b+k<n))return false;
    if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
    return true;
}
void SA(){
    for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
    for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
    for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
    for(int k=1;k<n;k<<=1){
        int num=0;
        for(int i=n-k;i<n;i++)y[num++]=i;
        for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
        for(int i=0;i<=m;i++)buc[i]=0;
        for(int i=0;i<n;i++)buc[x[y[i]]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
        swap(x,y);
        x[sa[0]]=num=0;
        for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
        m=num;
    }
    for(int i=0;i<n;i++)rk[sa[i]]=i;
    for(int i=0,k=0;i<n;i++){
        if(!rk[i])continue;
        if(k)k--;
        int j=sa[rk[i]-1];
        while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
        ht[rk[i]]=k;
    }
}
int main(){
    scanf("%d",&all);
    for(int i=1;i<=all;i++){
        scanf("%s",str);
        m=strlen(str);
        for(int j=0;j<m;j++)len[n]=m-j,id[n]=i,s[n]=str[j]-'a'+1,n++;
        s[n++]=i+26;
    }
    m=all+26;
    SA();
//  for(int i=0;i<n;i++)printf("%d ",id[sa[i]]);puts("");
//  for(int i=0;i<n;i++)printf("%d ",len[sa[i]]);puts("");
//  for(int i=0;i<n;i++)printf("%d ",ht[i]);puts("");
    for(int i=0,LCP=0;id[sa[i]];i++){
        LCP=min(LCP,ht[i]),res[id[sa[i]]]+=len[sa[i]]-ht[i];
        if(id[sa[i]]!=id[sa[i-1]])res[id[sa[i-1]]]-=ht[i],res[id[sa[i-1]]]+=LCP,LCP=ht[i];
    }
    for(int i=1;i<=all;i++)printf("%lld\n",res[i]);
    return 0;
}

XVIII.[HEOI2016/TJOI2016]字符串

作为一个理智正常的OIer，二维数点的题说什么都应该离线线段树通过而不是大力搞主席树呀（（（

我们发现这题询问中s[c,\dots,d]中这个“d”是不重要的，只需要把最终结果同(d-c+1)取\min即可，因此忽略不管。

然后这个问题就被转换成了：对于区间[a,b]内所有后缀suf[i]，求\min\Big(\operatorname{LCP}(suf[i],suf[c]),b-i+1\Big)的最大值。

我们考虑二分这个最大值，设为mid。现在要来判断mid这个值是否合法。则只有区间[a,a+mid-1]中的\operatorname{LCP}才可能达到这么长，故只要找到其中的\max\text{LCP}，如果其长度大于等于mid，则mid合法。

到现在我们已经可以构思出一个O(n\log^2n)的二分套线段树的做法了。具体思路是，因为\max\text{LCP}一定在两个后缀的rk最接近时取到，所以我们将它拆成两半，一半是rk_i\leq rk_c的，一半是rk_i\geq rk_c的。

则我们需要先将询问按照rk_c排序，按顺序将位置插入线段树，在前一半中查询区间中rk_i的最大值，后一半中查询rk_i的最小值（这里的线段树是以原串位置为下标的）。在查询到这个值最大值/最小值后，就可以通过ST表求出\text{LCP}了。当然，这一切都是建立在二分的基础上，即，我们每次询问的区间都是二分出来的区间[a,a+mid-1]。

但是这样子得写两棵线段树，再加上ST表，太难受了。我们不如这样，直接在线段树上维护\text{LCP}长度。办法很简单，当新加入一个位置后，直接将线段树中所有\text{LCP}长度与它取\min即可。

我们可以写出这样的pushdown函数：

#define change(x,y) seg[x].lcp=min(seg[x].lcp,y),seg[x].tag=min(seg[x].tag,y)
void pushdown(int x){
    change(lson,seg[x].tag),change(rson,seg[x].tag),seg[x].tag=0x3f3f3f3f;
}

然后在主函数只需要这样来一句change(1,ht[j])即可。

在取\min后，把对应位置的\text{LCP}长度改成n-i，因为自己跟自己的\text{LCP}长度就是串长。

这里是将一个位置插入线段树的代码：

void turnon(int x,int l,int r,int P){
    if(l>P||r<P)return;
    seg[x].lcp=max(seg[x].lcp,n-P);
    if(l!=r)pushdown(x),turnon(lson,l,mid,P),turnon(rson,mid+1,r,P);
}

到这里，我们已经省掉了ST表，并且也只用写一颗线段树了。我们要不再努力努力，干脆连二分也给省了，直接在线段树上二分？

我们设一个query函数来回答询问。我们考虑当前走到节点x，它代表的区间是[l,r]，询问区间是[L,R]。

1. 假如[l,r]\cup[L,R]=\emptyset，直接return -1即可。

2. 假如[l,r]\subseteq[L,R]：

2.1. 如果lcp_x\geq R-r+1，则显然全局最优答案肯定处于区间[l,r]之中，我们单独开一个getans函数来处理这种情况，马上讲。我们直接返回getans的结果，并标记找到了答案。

2.2 否则，lcp_x就是区间[l,r]中的最优答案（因为没有越界），直接return lcp[x]即可。

3. 否则，先递归左儿子，如果左儿子找到答案，直接return 左儿子的答案即可；否则，return max(左儿子的答案，右儿子的答案）

至于getans函数，就是一个常规的线段树上二分，找到最小的那个满足lcp[x]>=R-r+1的位置并返回即可。

这部分代码：

int getans(int x,int l,int r,int L,int R){//this function is to find the real answer in a section
    if(l==r)return min(seg[x].lcp,R-r+1);//we've reached a leaf, go back immediately.
    pushdown(x);
    if(seg[lson].lcp>=R-mid+1)return getans(lson,l,mid,L,R);//the answer in left son is surely the best
    else return max(seg[lson].lcp,getans(rson,mid+1,r,L,R));//the left answer hasn't gone over the border, so it's the real answer
}
int query(int x,int l,int r,int L,int R,bool &findans){//this function is to find the answer to the queries
    if(l>R||r<L)return -1;
    if(L<=l&&r<=R){
        if(seg[x].lcp>=R-r+1){findans=true;return getans(x,l,r,L,R);}//the answer here is the best answer
        return seg[x].lcp;//the answer has't gone over the border, so it's the real answer
    }
    pushdown(x);
    int tmp=query(lson,l,mid,L,R,findans);
    if(findans)return tmp;
    return max(tmp,query(rson,mid+1,r,L,R,findans));
}

正着来一遍，反着再来一遍，两边答案取\max即可。

总复杂度O(n\log n)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100100;
int n,m,q,res[N],len[N];
namespace Suffix_Array{
    int x[N],y[N],sa[N],ht[N],rk[N],buc[N];
    char s[N];
    bool mat(int a,int b,int k){
        if(y[a]!=y[b])return false;
        if((a+k<n)^(b+k<n))return false;
        if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
        return true;
    }
    void SA(){
        for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
        for(int k=1;k<n;k<<=1){
            int num=0;
            for(int i=n-k;i<n;i++)y[num++]=i;
            for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
            for(int i=0;i<=m;i++)buc[i]=0;
            for(int i=0;i<n;i++)buc[x[y[i]]]++;
            for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
            for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
            swap(x,y);
            x[sa[0]]=num=0;
            for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
            m=num;
        }
        for(int i=0;i<n;i++)rk[sa[i]]=i;
        for(int i=0,k=0;i<n;i++){
            if(!rk[i])continue;
            if(k)k--;
            int j=sa[rk[i]-1];
            while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
            ht[rk[i]]=k;
        }
    }   
}
using namespace Suffix_Array;
struct Query{
    int L,R,pos,id;
    Query(int a=0,int b=0,int c=0,int d=0){L=a,R=b,pos=c,id=d;}
    friend bool operator <(const Query&x,const Query&y){
        return x.pos<y.pos;
    }
}p[N];
namespace SegMentTree{
    #define lson x<<1
    #define rson x<<1|1
    #define mid ((l+r)>>1)
    struct SegTree{//lcp stands for the maximum lcp in the section 
        int lcp,tag;
    }seg[N<<2];
    #define change(x,y) seg[x].lcp=min(seg[x].lcp,y),seg[x].tag=min(seg[x].tag,y)
    void pushdown(int x){
        change(lson,seg[x].tag),change(rson,seg[x].tag),seg[x].tag=0x3f3f3f3f;
    }
    void build(int x,int l,int r){
        seg[x].tag=0x3f3f3f3f,seg[x].lcp=-1;
        if(l!=r)build(lson,l,mid),build(rson,mid+1,r);
    }
    void turnon(int x,int l,int r,int P){
        if(l>P||r<P)return;
        seg[x].lcp=max(seg[x].lcp,n-P);
        if(l!=r)pushdown(x),turnon(lson,l,mid,P),turnon(rson,mid+1,r,P);
    }
    int getans(int x,int l,int r,int L,int R){//this function is to find the real answer in a section
        if(l==r)return min(seg[x].lcp,R-r+1);//we've reached a leaf, go back immediately.
        pushdown(x);
        if(seg[lson].lcp>=R-mid+1)return getans(lson,l,mid,L,R);//the answer in left son is surely the best
        else return max(seg[lson].lcp,getans(rson,mid+1,r,L,R));//the left answer hasn't gone over the border, so it's the real answer
    }
    int query(int x,int l,int r,int L,int R,bool &findans){//this function is to find the answer to the queries
        if(l>R||r<L)return -1;
        if(L<=l&&r<=R){
            if(seg[x].lcp>=R-r+1){findans=true;return getans(x,l,r,L,R);}//the answer here is the best answer
            return seg[x].lcp;//the answer has't gone over the border, so it's the real answer
        }
        pushdown(x);
        int tmp=query(lson,l,mid,L,R,findans);
        if(findans)return tmp;
        return max(tmp,query(rson,mid+1,r,L,R,findans));
    }
    #undef lson
    #undef rson
    #undef mid
}
using namespace SegMentTree;
int main(){
    scanf("%d%d%s",&n,&q,s),m='z',SA();
    for(int i=1,a,b,c,d;i<=q;i++)scanf("%d%d%d%d",&a,&b,&c,&d),p[i]=Query(a-1,b-1,rk[c-1],i),len[i]=d-c+1;
    sort(p+1,p+q+1);
    build(1,0,n-1);
    for(int i=1,j=0;i<=q;i++){
        for(;j<=p[i].pos;j++)change(1,ht[j]),turnon(1,0,n-1,sa[j]);
        bool tmp=false;
        res[p[i].id]=max(res[p[i].id],query(1,0,n-1,p[i].L,p[i].R,tmp));
    }
    build(1,0,n-1);
    for(int i=q,j=n-1;i;i--){
        for(;j>=p[i].pos;j--)change(1,ht[j+1]),turnon(1,0,n-1,sa[j]);
        bool tmp=false;
        res[p[i].id]=max(res[p[i].id],query(1,0,n-1,p[i].L,p[i].R,tmp));
    }
    for(int i=1;i<=q;i++)printf("%d\n",min(res[i],len[i]));
    return 0;
}

XIX.工艺 /【模板】最小表示法

没啥好说的，直接倍长数组，然后后缀排序即可，道理都在IX.[JSOI2007]字符加密那儿讲过了。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=600100;
int n,m;
int s[N],x[N<<1],y[N<<1],buc[N],sa[N];
vector<int>v;
void SA(){
    for(int i=1;i<=n;i++)buc[x[i]=s[i]]++;
    for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
    for(int i=n;i;i--)sa[buc[x[i]]--]=i;
    for(int k=1;k<=n;k<<=1){
        int num=0;
        for(int i=n-k+1;i<=n;i++)y[++num]=i;
        for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
        for(int i=0;i<=m;i++)buc[i]=0;
        for(int i=1;i<=n;i++)buc[x[y[i]]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n;i;i--)sa[buc[x[y[i]]]--]=y[i];
        swap(x,y);
        x[sa[1]]=num=1;
        for(int i=2;i<=n;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
        if(n==num)break;
        m=num;
    }
}
void read(int &x){
    x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
int main(){
    read(n);
    for(int i=1;i<=n;i++)read(s[i]),s[i+n]=s[i],v.push_back(s[i]);
    sort(v.begin(),v.end()),v.resize(m=unique(v.begin(),v.end())-v.begin());
    n<<=1;
    for(int i=1;i<=n;i++)s[i]=lower_bound(v.begin(),v.end(),s[i])-v.begin()+1;
    SA();
    for(int i=1;i<=n;i++){
        if(n-sa[i]+1<(n>>1))continue;
        for(int j=1;j<=(n>>1);j++)printf("%d ",v[s[sa[i]+j-1]-1]);puts("");
        break;
    }
    return 0;
} 

XX.【模板】后缀自动机 (SAM)

俗话说的好，模板题怎么能用模板水过去呢

我们考虑用建出ht数组，然后用单调栈求出每个ht最多能向左向右延伸多远（VI.[AHOI2013]差异），然后直接一边扫过求\max即可。

复杂度O(n)，假如你用DC3的话。但是用倍增实际跑起来也真的超快！！！

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1001000;
int n,m;
int x[N],y[N],sa[N],ht[N],rk[N],buc[N];
char s[N];
bool mat(int a,int b,int k){
    if(y[a]!=y[b])return false;
    if((a+k<n)^(b+k<n))return false;
    if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
    return true;
}
void SA(){
    for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
    for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
    for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
    for(int k=1;k<n;k<<=1){
        int num=0;
        for(int i=n-k;i<n;i++)y[num++]=i;
        for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
        for(int i=0;i<=m;i++)buc[i]=0;
        for(int i=0;i<n;i++)buc[x[y[i]]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
        swap(x,y);
        x[sa[0]]=num=0;
        for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
        if(num>=n-1)break;
        m=num;
    }
    for(int i=0;i<n;i++)rk[sa[i]]=i;
    for(int i=0,k=0;i<n;i++){
        if(!rk[i])continue;
        if(k)k--;
        int j=sa[rk[i]-1];
        while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
        ht[rk[i]]=k;
    }
}
int L[N],R[N],stk[N],tp;
ll res;
int main(){
    scanf("%s",s),n=strlen(s),m='z';
    SA();
    for(int i=1;i<n;i++){
        while(tp&&ht[stk[tp]]>ht[i])R[stk[tp]]=i,tp--;
        L[i]=stk[tp],stk[++tp]=i;
    }
    while(tp)R[stk[tp--]]=n;
    for(int i=1;i<n;i++)res=max(res,1ll*ht[i]*(R[i]-L[i]));
    printf("%lld\n",res);
    return 0;
}

XXI.[NOI2016]优秀的拆分

这后缀数组越来越像一个用来求\operatorname{LCP}的工具人了……

对于一个\text{AABB}的拆分，我们可以在中间切一刀，变成\text{AA}与\text{BB}两半。这时，我们只需要设a_i表示以i为结尾的\text{AA}串数量，b_i表示以i开头的\text{BB}串数量，则答案即为\sum a_ib_{i+1}。

显然，这个可以通过hash做到n^2，并且可以取得95\%的好成绩，毫无区分意义。

然后就是一个非常神仙的思路了：

我们枚举一个长度len，然后每隔len个字符设立一个关键点。则任何长度\geq2len的子串都经过且只经过两个关键点。则我们枚举每一对相邻的关键点，并尝试求出有多少个合法子串经过了它。

我们求出这两个关键点的\operatorname{LCP}与\operatorname{LCS(Longest Common Suffix)}，这可以直接使用后缀数组+ST表求出。如果它们的和\geq len，则显然就有合法的串经过它们，这一数量为\operatorname{LCP}+\operatorname{LCS}-len+1个。我们只需要差分就可以得到a与b数组。

因为\sum\limits_{i=1}^n\dfrac{n}{i}=n\log n，所以该算法复杂度即为O(n\log n)。

记得清空所有数组！！！

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=30100;
int T,n,a[N],b[N];
ll res;
char str[N];
struct Suffix_Array{
    int x[N],y[N],buc[N],sa[N],ht[N],rk[N],LG[N],mn[N][16],m;
    char s[N];
    void init(){
        for(int i=0;i<N;i++)x[i]=y[i]=buc[i]=sa[i]=ht[i]=rk[i]=LG[i]=0;
        memset(mn,0,sizeof(mn));
        m='z';
    }
    bool mat(int a,int b,int k){
        if(y[a]!=y[b])return false;
        if((a+k<n)^(b+k<n))return false;
        if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
        return true;
    }
    void SA(){
        for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
        for(int k=1;k<n;k<<=1){
            int num=0;
            for(int i=n-k;i<n;i++)y[num++]=i;
            for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
            for(int i=0;i<=m;i++)buc[i]=0;
            for(int i=0;i<n;i++)buc[x[y[i]]]++;
            for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
            for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
            swap(x,y);
            x[sa[0]]=num=0;
            for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
            if(num>=n-1)break;
            m=num;
        }
        for(int i=0;i<n;i++)rk[sa[i]]=i;
        for(int i=0,k=0;i<n;i++){
            if(!rk[i])continue;
            if(k)k--;
            int j=sa[rk[i]-1];
            while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
            ht[rk[i]]=k;
        }
        for(int i=2;i<n;i++)LG[i]=LG[i>>1]+1;
        for(int i=1;i<n;i++)mn[i][0]=ht[i];
        for(int j=1;j<=LG[n-1];j++)for(int i=1;i+(1<<j)-1<n;i++)mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
    }
    int RMQ(int l,int r){
        if(l>=n||r>=n||l<0||r<0)return 0;
        l=rk[l],r=rk[r];
        if(l>r)swap(l,r);
        l++;
        int k=LG[r-l+1];
        return min(mn[l][k],mn[r-(1<<k)+1][k]);
    }
}pre,suf;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%s",str),n=strlen(str),memset(a,0,sizeof(a)),memset(b,0,sizeof(b)),res=0;
        pre.init(),suf.init();
        memcpy(pre.s,str,sizeof(str)),memcpy(suf.s,str,sizeof(str)),reverse(pre.s,pre.s+n);
//      printf("%s\n%s\n",pre.s,suf.s);
        pre.SA(),suf.SA();
//      for(int i=0;i<n;i++)printf("%d ",pre.rk[i]);puts("");
//      for(int i=0;i<n;i++)printf("%d ",suf.rk[i]);puts("");
        for(int len=1;len<=n/2;len++)for(int i=0;i+len<n;i+=len){
            int p=i,q=i+len,r=n-q,s=n-p;
            int LCP=min(suf.RMQ(p,q),len);
            int LCS=min(pre.RMQ(r,s),len-1);
            int Delta=LCP+LCS-len+1;
            if(Delta>=0)b[p-LCS]++,b[p-LCS+Delta]--,a[q+LCP-Delta]++,a[q+LCP]--;
        }
//      for(int i=0;i<n;i++)printf("(%d %d)\n",a[i],b[i]);
        for(int i=1;i<n;i++)a[i]+=a[i-1],b[i]+=b[i-1];
        for(int i=1;i<n;i++)res+=a[i-1]*b[i];
        printf("%lld\n",res);
    }
    return 0;
}

XXII.[湖南集训]图森

题解

XXIII.[NOI2018]你的名字

题解

XXIV.CF123D String

没啥好说的，直接建出笛卡尔树出来，然后统计一下和即可。复杂度O(n)，假如你用DC3的话。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100100;
int n,m;
int x[N],y[N],buc[N],sa[N],ht[N],rk[N];
char s[N];
bool mat(int a,int b,int k){
    if(y[a]!=y[b])return false;
    if((a+k<n)^(b+k<n))return false;
    if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
    return true;
}
void SA(){
    for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
    for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
    for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
    for(int k=1;k<n;k<<=1){
        int num=0;
        for(int i=n-k;i<n;i++)y[num++]=i;
        for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
        for(int i=0;i<=m;i++)buc[i]=0;
        for(int i=0;i<n;i++)buc[x[y[i]]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
        swap(x,y);
        x[sa[0]]=num=0;
        for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
        if(num>=n-1)break;
        m=num;
    }
    for(int i=0;i<n;i++)rk[sa[i]]=i;
    for(int i=0,k=0;i<n;i++){
        if(!rk[i])continue;
        if(k)k--;
        int j=sa[rk[i]-1];
        while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
        ht[rk[i]]=k;
    }
}
int stk[N],L[N],R[N],tp,lson[N],rson[N],rt;
ll res;
void solve(int x,int las){
    res+=1ll*(ht[x]-las)*(R[x]-L[x])*(R[x]-L[x]+1)/2;
    if(lson[x])solve(lson[x],ht[x]);
    else res+=(n-sa[L[x]])-ht[x];
    if(rson[x])solve(rson[x],ht[x]);
    else res+=(n-sa[R[x]-1])-ht[x];
}
int main(){
    scanf("%s",s),n=strlen(s),m='z';
    SA();
    for(int i=1;i<n;i++){
        while(tp&&ht[stk[tp]]>ht[i])lson[i]=stk[tp],R[stk[tp]]=i,tp--;
        if(tp)rson[stk[tp]]=i;
        L[i]=stk[tp],stk[++tp]=i;
    }
    while(tp)R[stk[tp--]]=n;
    rt=stk[1];
    solve(rt,0);
    printf("%lld\n",res);
    return 0;
}

XXV.[JSOI2015]串分割

题解

XXVI.SP7258 SUBLEX - Lexicographical Substring Search

在上一题中，我们二分了后缀；但这里，我们要二分的是子串。

我们设一个sum_x表示有多少本质不同子串的字典序小于等于sa_i。显然，它是单调增的。则我们可以二分找出sum_x小于询问的最右位置，输出即可。

虽然简单，但这是我们接下来很多题的基础。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100100;
typedef long long ll;
int q;
ll sum[N];
namespace Suffix_Array{
    int x[N],y[N],buc[N],sa[N],ht[N],rk[N],n,m;
    char s[N];
    bool mat(int a,int b,int k){
        if(y[a]!=y[b])return false;
        if((a+k<n)^(b+k<n))return false;
        if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
        return true;
    }
    void SA(){
        for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
        for(int k=1;k<n;k<<=1){
            int num=0;
            for(int i=n-k;i<n;i++)y[num++]=i;
            for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
            for(int i=0;i<=m;i++)buc[i]=0;
            for(int i=0;i<n;i++)buc[x[y[i]]]++;
            for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
            for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
            swap(x,y);
            x[sa[0]]=num=0;
            for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
            if(num>=n-1)break;
            m=num;
        }
        for(int i=0;i<n;i++)rk[sa[i]]=i;
        for(int i=0,k=0;i<n;i++){
            if(!rk[i])continue;
            if(k)k--;
            int j=sa[rk[i]-1];
            while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
            ht[rk[i]]=k;
        }
    }
}
using namespace Suffix_Array; 
int main(){
    scanf("%s%d",s,&q),n=strlen(s),m='z';
    SA();
    sum[0]=n-sa[0];
    for(int i=1;i<n;i++)sum[i]=sum[i-1]+(n-sa[i])-ht[i];
//  for(int i=0;i<n;i++)printf("%d ",sum[i]);puts("");
    for(int x;q--;){
        scanf("%d",&x);
        int p=lower_bound(sum,sum+n,x)-sum;
        for(int i=0;i<x-sum[p-1]+ht[p];i++)putchar(s[sa[p]+i]);putchar('\n');
    }
    return 0;
} 

XXVII.[BZOJ4310]跳蚤

我们仍然考虑二分子串。设当前二分的子串从位置pos开始，长度为len。考虑如何编写check函数。

一个naive的想法便是从前往后枚举所有极大的不存在小于二分串的子串的段，然后将该段数与规定段数作比较。

但是这有点问题——我们发现，这样做每次都是为段中所有后缀各添加一个字符，不好快速判断。但我们可以借鉴XIV.[SDOI2016]生成魔咒的思想，反过来倒序枚举极大段，这次每次都只是增加一个前缀了。

于是只要判断该前缀与二分串的字典序关系，如果字典序大于二分串就切一刀即可。

因为所有子串数是O(n^2)的，所以实际复杂度为O(n\log n^2)=O(n\times2\log n)=O(n\log n)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100100;
typedef long long ll;
ll sum[N];
int K;
namespace Suffix_Array{
    int x[N],y[N],buc[N],sa[N],ht[N],rk[N],n,m,LG[N],mn[N][20];
    char s[N];
    bool mat(int a,int b,int k){
        if(y[a]!=y[b])return false;
        if((a+k<n)^(b+k<n))return false;
        if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
        return true;
    }
    void SA(){
        for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
        for(int k=1;k<n;k<<=1){
            int num=0;
            for(int i=n-k;i<n;i++)y[num++]=i;
            for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
            for(int i=0;i<=m;i++)buc[i]=0;
            for(int i=0;i<n;i++)buc[x[y[i]]]++;
            for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
            for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
            swap(x,y);
            x[sa[0]]=num=0;
            for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
            if(num>=n-1)break;
            m=num;
        }
        for(int i=0;i<n;i++)rk[sa[i]]=i;
        for(int i=0,k=0;i<n;i++){
            if(!rk[i])continue;
            if(k)k--;
            int j=sa[rk[i]-1];
            while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
            ht[rk[i]]=k;
        }
        for(int i=2;i<n;i++)LG[i]=LG[i>>1]+1;
        for(int i=1;i<n;i++)mn[i][0]=ht[i];
        for(int j=1;j<=LG[n-1];j++)for(int i=1;i+(1<<j)-1<n;i++)mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
    }
    int LCP(int x,int y){
        if(x==y)return n-x;
        x=rk[x],y=rk[y];
        if(x>y)swap(x,y);
        x++;
        int k=LG[y-x+1];
        return min(mn[x][k],mn[y-(1<<k)+1][k]);
    }
}
using namespace Suffix_Array;
bool che(ll ip){
    int pos=lower_bound(sum,sum+n,ip)-sum,len=ip-sum[pos-1]+ht[pos];
    pos=sa[pos];
//  printf("%lld:%d,%d\n",ip,pos,len);
    int k=0;
    for(int i=n-1,j=n-1;i>=0;i=j,k++){//numerate backwards
        for(;j>=0;j--){
            int tmp=min({LCP(j,pos),i-j+1,len});//the minimum length possible
            if(tmp==i-j+1&&tmp<=len)continue;//is ok
            if(tmp==len)break;
            if(rk[j]>rk[pos])break;//a greater lexicographicity, break.
        }
        if(i==j)return false;//there's a SINGLE CHARACTER that is lexicographically greater than substring checked, so break out.
    }
    return k<=K;
}
int main(){
    scanf("%d%s",&K,s),n=strlen(s),m='z',SA();
//  for(int i=0;i<n;i++)printf("%d ",sa[i]);puts("");
    sum[0]=n-sa[0];
    for(int i=1;i<n;i++)sum[i]=sum[i-1]+(n-sa[i])-ht[i];
//  for(int i=0;i<n;i++)printf("%2d ",i);puts("");
//  for(int i=0;i<n;i++)printf("%2d ",s[i]-'a');puts(""); 
//  for(int i=0;i<n;i++)printf("%d ",sum[i]);puts("");
    ll l=1,r=sum[n-1];
    while(l<r){
        ll mid=(l+r)>>1;
        if(che(mid))r=mid;
        else l=mid+1;
    }
    int pos=lower_bound(sum,sum+n,l)-sum,len=l-sum[pos-1]+ht[pos];
    for(int i=0;i<len;i++)putchar(s[sa[pos]+i]);
    return 0;
} 
/*
3
ihgjhdgajhdjfjddddfdj
*/

XXVIII.[BZOJ3277]串/CF204E Little Elephant and Strings

这两题是重题，代码改都不改交上去就能A，故放在一起讲。

网上的大多数SA题解都是O(n\log^2n)或O(n\log n)的复杂度，太令人不爽了。因此，这里有一种复杂度O(n)的SA题解。

一看到O(n)的SA，就应该猜出我们的目标是什么了——笛卡尔树。但是这里我们就要判断笛卡尔树的区间内部出现了多少条不同的原串。在之前的X.[SCOI2012]喵星球上的点名中，我们使用了O(n\log n)的二维数点来解决此类问题。但是这题的K是固定的，所以有没有更优美的方法呢？

有的！我们可以用two-pointers求出对于每个位置x，它左侧最右边的一个位置lft_x且使得[lft_x,x]中出现了恰好K个不同的原串。则我们如果要再来判断区间[L,R]是否合法的话，只需要判断是否有L\leq lft_R即可。

使用单调栈建笛卡尔树+two-pointers求lft+差分计算贡献+DC3后缀排序，即可将复杂度压至O(n)。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200100;
int n,m,id[N],A,B,len[N];
int x[N],y[N],buc[N],sa[N],ht[N],rk[N],s[N];
char str[N];
bool mat(int a,int b,int k){
    if(y[a]!=y[b])return false;
    if((a+k<n)^(b+k<n))return false;
    if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
    return true;
}
void SA(){
    for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
    for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
    for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
    for(int k=1;k<n;k<<=1){
        int num=0;
        for(int i=n-k;i<n;i++)y[num++]=i;
        for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
        for(int i=0;i<=m;i++)buc[i]=0;
        for(int i=0;i<n;i++)buc[x[y[i]]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
        swap(x,y);
        x[sa[0]]=num=0;
        for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
        if(num>=n-1)break;
        m=num;
    }
    for(int i=0;i<n;i++)rk[sa[i]]=i;
    for(int i=0,k=0;i<n;i++){
        if(!rk[i])continue;
        if(k)k--;
        int j=sa[rk[i]-1];
        while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
        ht[rk[i]]=k;
    }
}
int lft[N],occ[N];
int L[N],R[N],lson[N],rson[N],stk[N],tp;
int diff[N];
ll res[N];
void solve(int x,int las){
//  printf("%d:[%d,%d]:%d-%d\n",x,L[x],R[x],las,ht[x]);
    int tmp;
    if(L[x]<=lft[R[x]-1])tmp=ht[x]-las,diff[L[x]]+=tmp,diff[R[x]]-=tmp/*,printf("A:%d:[%d,%d]:%d\n",x,L[x],R[x]-1,tmp)*/;
    if(lson[x])solve(lson[x],ht[x]);
    else if(B==1)tmp=len[sa[L[x]]]-ht[x],diff[L[x]]+=tmp,diff[L[x]+1]-=tmp/*,printf("B:%d:[%d,%d]:%d\n",x,L[x],L[x],tmp)*/;
    if(rson[x])solve(rson[x],ht[x]);
    else if(B==1)tmp=len[sa[R[x]-1]]-ht[x],diff[R[x]-1]+=tmp,diff[R[x]]-=tmp/*,printf("C:%d:[%d,%d]:%d\n",x,R[x]-1,R[x]-1,tmp)*/;
}
int main(){
    scanf("%d%d",&A,&B);
    for(int i=1;i<=A;i++){
        scanf("%s",str),m=strlen(str);
        for(int j=0;j<m;j++)s[n]=str[j]-'a'+1,id[n]=i,len[n]=m-j,n++;
        s[n++]=i+26;
    }
//  for(int i=0;i<n;i++)printf("%2d ",s[i]);puts("");
    m=A+26;
    SA();
//  for(int i=0;i<n;i++)printf("%2d ",sa[i]);puts("");
//  for(int i=0;i<n;i++)printf("%d ",id[sa[i]]);puts("");
//  for(int i=0;i<n;i++)printf("%d ",ht[i]);puts("");
    for(int i=0,j=0,k=0;j<n;j++){
        if(id[sa[j]])k+=!occ[id[sa[j]]]++;
        for(;k>=B;i++)if(id[sa[i]])k-=!--occ[id[sa[i]]];
        lft[j]=i-1;
    }
//  for(int i=0;i<n;i++)printf("%d ",lft[i]);puts("");
    for(int i=1;i<n;i++){
        while(tp&&ht[stk[tp]]>ht[i])lson[i]=stk[tp],R[stk[tp]]=i,tp--;
        if(tp)rson[stk[tp]]=i;
        L[i]=stk[tp],stk[++tp]=i;
    }
    while(tp)R[stk[tp--]]=n;
//  for(int i=1;i<n;i++)printf("[%d,%d]",L[i],R[i]);puts("");
    solve(stk[1],0);
    for(int i=1;i<n;i++)diff[i]+=diff[i-1];
//  for(int i=0;i<n;i++)printf("%d ",diff[i]);puts("");
    for(int i=0;i<n;i++)if(id[sa[i]])res[id[sa[i]]]+=diff[i];
    for(int i=1;i<=A;i++)printf("%lld ",res[i]);
    return 0;
}

XXIX.CF700E Cool Slogans

题解

XXX.[CTSC2012]熟悉的文章

题解

XXXI.CF666E Forensic Examination

题解

XXXII.CF1063F String Journey

题解

XXXIII.CF547E Mike and Friends

实际上是一道很蠢的问题。

我们直接在后缀数组上二分，求出所有拥有串s_k作为前缀的后缀所在的区间，则问题就被转换为某一区间中值在[l,r]范围内的数的个数。显然是二维数点问题，于是直接离线后树状数组解决。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=500100;
typedef long long ll;
int A,B,id[N],len[N],pos[N];
namespace Suffix_Array{
    int x[N],y[N],buc[N],sa[N],ht[N],rk[N],n,m,mn[N][20],LG[N],s[N];
    char str[N];
    bool mat(int a,int b,int k){
        if(y[a]!=y[b])return false;
        if((a+k<n)^(b+k<n))return false;
        if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
        return true;
    }
    void SA(){
        for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
        for(int k=1;k<n;k<<=1){
            int num=0;
            for(int i=n-k;i<n;i++)y[num++]=i;
            for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
            for(int i=0;i<=m;i++)buc[i]=0;
            for(int i=0;i<n;i++)buc[x[y[i]]]++;
            for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
            for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
            swap(x,y);
            x[sa[0]]=num=0;
            for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
            if(num>=n-1)break;
            m=num;
        }
        for(int i=0;i<n;i++)rk[sa[i]]=i;
        for(int i=0,k=0;i<n;i++){
            if(!rk[i])continue;
            if(k)k--;
            int j=sa[rk[i]-1];
            while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
            ht[rk[i]]=k;
        }
        for(int i=2;i<n;i++)LG[i]=LG[i>>1]+1;
        for(int i=1;i<n;i++)mn[i][0]=ht[i];
        for(int j=1;j<=LG[n-1];j++)for(int i=1;i+(1<<j)-1<n;i++)mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
    }
    int LCP(int x,int y){
        if(x>y)swap(x,y);
        x++;
        int k=LG[y-x+1];
        return min(mn[x][k],mn[y-(1<<k)+1][k]);
    }
    void Range(int x,int k,int &L,int &R){
        int l,r;
        x=rk[x];
        l=0,r=x;
        while(l<r){
            int mid=(l+r)>>1;
            if(LCP(mid,x)>=k)r=mid;
            else l=mid+1;
        }
        L=r;
        l=x,r=n-1;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(LCP(mid,x)>=k)l=mid;
            else r=mid-1;
        }
        R=l;
    }
}
using namespace Suffix_Array;
struct Query{
    int x,l,r,id;
    Query(int _1=0,int _2=0,int _3=0,int _4=0){x=_1,l=_2,r=_3,id=_4;}
    friend bool operator <(const Query &x,const Query &y){
        return x.x<y.x;
    }
}q[N<<1];
int res[N],t[N];
void ADD(int x){while(x<=A)t[x]++,x+=x&-x;}
int SUM(int x){int sum=0;while(x)sum+=t[x],x-=x&-x;return sum;}
int main(){
    scanf("%d%d",&A,&B);
    for(int i=1;i<=A;i++){
        scanf("%s",str),m=strlen(str),len[i]=m,pos[i]=n;
        for(int j=0;j<m;j++)s[n]=str[j]-'a'+1,id[n]=i,n++;
        s[n++]=i+26;
    }
    m=A+26;
    SA();
    for(int i=1,a,b,c,d;i<=B;i++){
        scanf("%d%d%d",&c,&d,&a);
        Range(pos[a],len[a],a,b);
        q[i]=Query(a-1,c,d,-i);
        q[i+B]=Query(b,c,d,i);
    }
    sort(q+1,q+(B<<1)+1);
    for(int i=0,j=1;i<n;i++){
        if(id[sa[i]])ADD(id[sa[i]]);
        while(j<=(B<<1)&&q[j].x<i)j++;
        while(j<=(B<<1)&&q[j].x==i){
            int tmp=SUM(q[j].r)-SUM(q[j].l-1);
            if(q[j].id<0)res[-q[j].id]-=tmp;
            else res[q[j].id]+=tmp;
            j++;
        }
    }
    for(int i=1;i<=B;i++)printf("%d\n",res[i]);
    return 0;
}

XXXIV.CF653F Paper task

比较常规的一道题吧。

首先，我们先不考虑“匹配”这一条件，光考虑“不同子串”，就是I.不同子串个数。

现在我们考虑匹配了，则显然，假设我们现在枚举到位置i，则只有区间[sa_i+ht_i,n]范围内的端点才是合法的。

怎样判断匹配呢？这里就有一个小技巧了：

我们把(看作+1，)看作-1，然后作一个前缀和，记作s_i。则子串[l,r]合法，当且仅当s_{l-1}=s_r，并且\nexists j\in[l,r],s_j<s_r。

于是我们就可以用ST表+二分找出这个最远的符合条件的r。然后，可以用vector存储所有s_i=k的位置，最后只要在区间[sa_i+ht_i,r]中二分找出所有位置的数量即可。

时间复杂度O(n\log n)。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500100;
int n,m;
namespace Suffix_Array{
    int x[N],y[N],buc[N],sa[N],rk[N],ht[N];
    char s[N];
    bool mat(int a,int b,int k){
        if(y[a]!=y[b])return false;
        if((a+k<=n)^(b+k<=n))return false;
        if((a+k<=n)&&(b+k<=n))return y[a+k]==y[b+k];
        return true;
    }
    void SA(){
        for(int i=1;i<=n;i++)buc[x[i]=s[i]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n;i;i--)sa[buc[x[i]]--]=i;
        for(int k=1;k<=n;k<<=1){
            int num=0;
            for(int i=n-k+1;i<=n;i++)y[++num]=i;
            for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
            for(int i=0;i<=m;i++)buc[i]=0;
            for(int i=1;i<=n;i++)buc[x[y[i]]]++;
            for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
            for(int i=n;i;i--)sa[buc[x[y[i]]]--]=y[i];
            swap(x,y);
            x[sa[1]]=num=1;
            for(int i=2;i<=n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
            if(n==num)break;
            m=num;
        }
        for(int i=1;i<=n;i++)rk[sa[i]]=i;
        for(int i=1,k=0;i<=n;i++){
            if(rk[i]==1)continue;
            if(k)k--;
            int j=sa[rk[i]-1];
            while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])k++;
            ht[rk[i]]=k;
        }
    }
}
using namespace Suffix_Array;
int LG[N],ST[N][20];
int RMQ(int l,int r){
    int k=LG[r-l+1];
    return min(ST[l][k],ST[r-(1<<k)+1][k]);
}
vector<int>v[N<<1];
ll res;
int main(){
    scanf("%d%s",&n,s+1),m=')',SA();
    for(int i=1;i<=n;i++)ST[i][0]=(s[i]==')'?ST[i-1][0]-1:ST[i-1][0]+1),v[ST[i][0]+n].push_back(i);
    for(int i=2;i<=n;i++)LG[i]=LG[i>>1]+1;
    for(int j=1;j<=LG[n];j++)for(int i=1;i+(1<<j)-1<=n;i++)ST[i][j]=min(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
    for(int i=1;i<=n;i++){
        int l=sa[i]+ht[i]-1,r=n;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(RMQ(sa[i],mid)>=ST[sa[i]-1][0])l=mid;
            else r=mid-1;
        }
        int pos=ST[sa[i]-1][0]+n;
        res+=upper_bound(v[pos].begin(),v[pos].end(),l)-upper_bound(v[pos].begin(),v[pos].end(),sa[i]+ht[i]-1);
    }
    printf("%lld\n",res);
    return 0;
}

XXXV.树上后缀排序

My Solution