考虑在后面新加一个字母产生的影响

假设是第i个

如果不考虑重复，那么会增加i个不同的字符串

考虑重复的话，就是找到 最小的j，满足s[j……i] 在之前出现过，那么i的贡献就是j-1

 即查找与某个串的最长公共后缀

如果把整个串倒过来，就变成了每次在前面加一个，查找最长公共前缀

这个利用后缀数组的height数组可以解决

有一个很显然的结论是：

若ijk满足  rank(i)<rank(j)<rank(k)   或者 rank(i)>rank(j)>rank(k) ，则LCP(i,j)>=LCP(i,k)

所以每次找到 排名在它前面的 第一个串，找到排名在它后面的第一个串

这个串分别与他们求LCS，取大的那个，就是加入i后的重复的串

求LCS用height数组+RMQ，

找排名在它前/后的第一个串可以用平衡树/set

网上看的题解用的树状数组

第一个树状数组 找前面的第一个串，权值=位置，这样找rk[i] 前面最大的即可

第二个树状数组 找后面的第一个串，权值=n-位置+1，就是倒着的，这样就是找n-rk[i] 前面最大的 

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define N 100001#define lowbit(x) (x&-x)int n,tot;int a[N],has[N];int v[N];int sa[2][N],rk[2][N];int height[N];int p,q=1;int F[N][17];int c[2][N];void read(int &x){    x=0; char c=getchar();    while(!isdigit(c)) c=getchar();    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}void mul(int k,int *sa,int *rk,int *SA,int *RK){    for(int i=1;i<=n;++i) v[rk[sa[i]]]=i;    for(int i=n;i;--i) if(sa[i]-k>0) SA[v[rk[sa[i]-k]]--]=sa[i]-k;    for(int i=n-k+1;i<=n;++i) SA[v[rk[i]]--]=i;    for(int i=1;i<=n;++i)     RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i-1]+k]!=rk[SA[i]+k] || rk[SA[i-1]]!=rk[SA[i]]);}void presa(){    memset(v,0,sizeof(v));    for(int i=1;i<=n;++i) v[a[i]]++;    for(int i=1;i<=tot;++i) v[i]+=v[i-1];    for(int i=1;i<=n;++i) sa[p][v[a[i]]--]=i;    for(int i=1;i<=n;++i) rk[p][sa[p][i]]=rk[p][sa[p][i-1]]+(a[sa[p][i-1]]!=a[sa[p][i]]);    for(int k=1;k
          
           <<=1,swap(p,q)) mul(k,sa[p],rk[p],sa[q],rk[q]);}void get_height(){ int k=0,j; for(int i=1;i<=n;++i) { j=sa[p][rk[p][i]-1]; while(i+k<=n && j+k<=n && a[i+k]==a[j+k]) k++; height[rk[p][i]]=k; if(k) k--; }}int change(int w,int r){ for(int i=r;i<=n;i+=lowbit(i)) c[w][i]=max(c[w][i],r);}int ask(int w,int r){ int ans=0; for(int i=r;i;i-=lowbit(i)) ans=max(ans,c[w][i]); return ans;}int rmq(int l,int r){ int k=log2(r-l+1); return min(F[l][k],F[r-(1<
           
            =1) lcs=max(lcs,rmq(pre+1,pos)); if(suc<=n) lcs=max(lcs,rmq(pos+1,suc)); ans+=n-i+1-lcs; cout<
            
             <<'\n'; change(0,pos); change(1,n-pos+1); }}int main(){ read(n); for(int i=n;i;--i) read(a[i]),has[i]=a[i]; sort(has+1,has+n+1); tot=unique(has+1,has+n+1)-has-1; for(int i=1;i<=n;++i) a[i]=lower_bound(has+1,has+tot+1,a[i])-has; presa(); get_height(); solve(); fclose(stdin); fclose(stdout); return 0;}