题链：

题解：

把串反过来后，问题变为求每个后缀的互不相同的子串个数。

首先用倍增算法求出 sa[],rank[],height[]，然后对 height[]数组建立 ST表。

接着求出整个串的子串个数，ans+=N-sa[i]-height[i]。(我从0开始编号的)

式子的含义就是考虑每个后缀相比它的前一名，多了几个与之前不同的且串头为该后缀的头的子串。

（一定要清晰地懂得并理解那个式子哦）

之前得出了0 位置开始的后缀(即整个串)的子串个数，

那么现在就需要把 rank[0]这个后缀从排好序的后缀数组中去除。

然后维护出新的后缀(即从1位置开始的后缀)的子串个数。

怎么做呢，反向考虑 ans的求法:

即把rank[0]产生的贡献减去(包括和它上面一名以及和它下面一名产生的贡献),相当于该后缀被去除了。

这时排在rank[0]上面一位的后缀(设为 u),和排在rank[0]下面一位的后缀(设为 d)，

就挨在了一起，那么要加上 u 后缀和 d 后缀的贡献。

然后就得到了新的后缀的子串个数。

之后的其它后缀的计算就类似了。

另外再提一下，在找当前后缀的上一名后缀和下一名后缀时，找到的必须是还在后缀数组中(即还没有被去除)，

可以用类似并查集的思想维护(好吧，是路径压缩的思想)，做到均摊 O(1)。

除开倍增算法和求ST表的复杂度 O(N)

代码：

#include
    
     #include
     
      #include
      
       #include
       
        #define MAXN 100500#define filein(x) freopen(#x".in","r",stdin);#define fileout(x) freopen(#x".out","w",stdout);using namespace std;int sa[MAXN],rak[MAXN],hei[MAXN];int up[MAXN],down[MAXN],A[MAXN],log2[MAXN],stm[MAXN][20];bool vis[MAXN];void build(int N,int M){	static int cc[MAXN],ta[MAXN],tb[MAXN],*x,*y,h,p;	x=ta; y=tb; h=0; A[N]=-1;	for(int i=0;i
        
         =0;i--) sa[--cc[x[i]]]=i;	for(int k=1;p=0,k
         
          <<=1){ for(int i=N-k;i
          
           =k) y[p++]=sa[i]-k; for(int i=0;i
           
            =0;i--) sa[--cc[x[y[i]]]]=y[i]; swap(x,y); y[N]=-1; x[sa[0]]=0; M=1; for(int i=1;i
            
             =N) break; } for(int i=0;i
             
              r) swap(l,r); l++; k=log2[r-l+1]; return min(stm[l+(1<
              
               >1]+1; int N,cnt; scanf("%d",&N); for(int i=N-1;i>=0;i--) scanf("%d",&A[i]),tmp[i]=A[i]; sort(tmp,tmp+N); cnt=unique(tmp,tmp+N)-tmp; for(int i=0;i