后缀数组好题。

 

差分不用说了。统计形如ABA的数量。

按照什么顺序统计答案呢？

 

枚举B的左端点？但是位置连续，并不代表sa的位置连续，所以难以往两边统计A部分的贡献。

我们转而枚举A的长度和起始位置，直接这样做是O(n^2)的。考虑加速

 

正反做两遍SA，RMQ预处理min，便于O(1)查询lcp

枚举A的部分长度为L

我们每L个点设置一个关键点，

枚举每一个关键点i，另一个点j=i+L+B，设i，j两侧匹配的长度（lcp） 为l,r

那么，如果有l+r>=L,那么意味着在这里有l+r-L+1的长度为L的A部分可以做出贡献

为了不重不漏，l，r的长度和L取min，这样可以发现，相邻的(i,j)的起始点没有公共部分。

如果一个A部分满足匹配，那么一定能被一组(i,j)恰好覆盖一次。

 

至于为什么枚举L，再间隔L设置关键点，是因为长度至少是L的情况下，这样一定不重不漏。

如果间隔过大，那么可能中间漏掉一些，如果不和L取min，把上界放宽，可能会重复或者遗漏。

间隔过小，和L取min也会重复，而且本身枚举次数增多还会TLE

 

由于L的限制，使得每一个部分最少长度要有L，所以每相邻L个位置一次统计，一定不会有遗漏。

说白了，就是用了一个trick，在O(nlogn)的时间内，不重不漏统计了答案。

 

画一画图，细节处理好，就没了。

#include
     
      #define reg register int#define il inline#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(ll &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=50005;ll n,m;int lg[2*N];struct hou{    ll s[N];    int x[N],y[N],c[N],sa[N],rk[N],hei[N];    int f[N][18];    void SA(){        int m=50002;        for(reg i=1;i<=n;++i) ++c[x[i]=s[i]];        for(reg i=2;i<=m;++i) c[i]+=c[i-1];        for(reg i=1;i<=n;++i) sa[c[x[i]]--]=i;        for(reg k=1;k<=n;k<<=1){            int num=0;            for(reg i=n-k+1;i<=n;++i) y[++num]=i;            for(reg i=1;i<=n;++i){                if(sa[i]-k>=1) y[++num]=sa[i]-k;            }            for(reg i=1;i<=m;++i) c[i]=0;            for(reg i=1;i<=n;++i) ++c[x[i]];            for(reg i=1;i<=m;++i) c[i]+=c[i-1];            for(reg i=n;i>=1;--i) sa[c[x[y[i]]]--]=y[i],y[i]=0;            for(reg i=1;i<=n;++i){                swap(x[i],y[i]);            }            num=1;            x[sa[1]]=1;            for(reg 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;            if(num==n) break;        }    }    void HEI(){        for(reg i=1;i<=n;++i) rk[sa[i]]=i;        int k=0;        for(reg i=1;i<=n;++i){            if(k) --k;            if(rk[i]==1) continue;            int j=sa[rk[i]-1];            while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) ++k;            hei[rk[i]]=k;        }    }    void build(){        SA();HEI();    //  cout<<" nn "<
      
       <
       
        y) swap(x,y);    //  cout<<" rk "<
        
         <<" "<
         
          <
          
           =1;--i) a[i]-=a[i-1],b[++cnt]=a[i]; sort(b+1,b+cnt+1); cnt=unique(b+1,b+cnt+1)-b-1; for(reg i=1;i<=n;++i) { a[i]=lower_bound(b+1,b+cnt+1,a[i])-b; if(i!=1)A.s[i-1]=a[i],B.s[n-i+1]=a[i];//warning!! n-1-i+1 }// for(reg i=1;i<=n;++i){// cout<
           
            <<" ";// }cout<
            
             >(lg[i-1]+1))?lg[i-1]+1:lg[i-1]; ll ans=0; for(reg L=1;L<=n;++L){ // cout<<" L -----------------"<
             
              <
              
               n) break; // cout<<"ii ******* "<
               <<" "<
                
                 <
                 
                  =L){ ans+=tmp-L+1; } } // cout<<" ans "<
                  
                   <
                  
                 
                
              
             
            
           
          
         
        
       
      
     

 总结：

这种找关键点左右统计贡献的题目还是头一次见到。

感觉好处是配合上L的长度，可以比较有序且不重不漏统计一些贡献。