BZOJ 2119 股市的预测 (后缀数组+RMQ)

题目大意：求一个字符串中形如$ABA$的串的数量，其中$B$的长度是给定的

有点像[NOI2016]优秀的拆分这道题

先对序列打差分，然后离散，再正反跑$SA$，跑出$st$表

进入正题

$ABA$串有一个神奇的性质

令$A$串长度是$x$

如果我们选取了一个位置$i$，再选取一个位置$i+x+m$

用预处理的$st$表，求出经过它们的，最长的相同子串的起始位置$s$和结束位置$e$

合法的$ABA$串似乎在$[s,e]$之间滑动

有了这个性质，我们再外层枚举长度$x$，在序列中找出一些相隔为$x$的关键点，求滑动窗口的左$A$串部分，每次当且仅当覆盖一个关键点时，能覆盖的最长距离总和

总时间$O(n(lnn+logn))$

别像我一样把RMQ打错还调了20min

 #include <map>

 #include <cmath>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N1 50500

 #define ll long long

 #define uint unsigned int

 #define rint register int

 #define il inline

 #define it map<int,int>::iterator

 #define inf 0x3f3f3f3f

 using namespace std;

 int gint()

 {

     int ret=,fh=;char c=getchar();

     while(c<''||c>''){if(c=='-')fh=-;c=getchar();}

     while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}

     return ret*fh;

 }

 int n,m,len,nn;

 int lg[N1];

 struct SA{

 int a[N1],tr[N1],rk[N1],hs[N1],sa[N1],h[N1],f[N1][];

 int check(int i,int j,int k){

     if(i+k>len||j+k>len) return ;

     return (rk[i]==rk[j]&&rk[i+k]==rk[j+k])?:;

 }

 void Pre()

 {

     rint i,cnt=;

     for(i=;i<=len;i++) hs[a[i]]++;

     for(i=;i<=nn;i++) if(hs[i]) tr[i]=++cnt;

     for(i=;i<=nn;i++) hs[i]+=hs[i-];

     for(i=;i<=len;i++) rk[i]=tr[a[i]],sa[hs[a[i]]--]=i;

     for(int k=;cnt<len;k<<=)

     {

         for(i=;i<=cnt;i++) hs[i]=;

         for(i=;i<=len;i++) hs[rk[i]]++;

         for(i=;i<=cnt;i++) hs[i]+=hs[i-];

         for(i=len;i>=;i--) if(sa[i]>k) tr[sa[i]-k]=hs[rk[sa[i]-k]]--;

         for(i=;i<=k;i++)  tr[len-i+]=hs[rk[len-i+]]--;

         for(i=;i<=len;i++) sa[tr[i]]=i;

         for(i=,cnt=;i<=len;i++) tr[sa[i]]=check(sa[i],sa[i-],k)?cnt:++cnt;

         for(i=;i<=len;i++) rk[i]=tr[i];

     }

     for(i=;i<=len;i++){

         if(rk[i]==) continue;

         for(int j=max(,h[rk[i-]]-);;j++)

             if(a[i+j-]==a[sa[rk[i]-]+j-]) h[rk[i]]=j;

             else break;

     }

     for(i=;i<=len;i++) f[i][]=h[i];

     for(int j=;j<=lg[len];j++)

         for(i=;i+(<<j)-<=len;i++)

             f[i][j]=min(f[i][j-],f[i+(<<(j-))][j-]);

 }

 int query(int i,int j){

     int x=rk[i],y=rk[j];

     if(x>y) swap(x,y);x++;int _L=y-x+;

     if(_L<) return ;

     return min(f[x][lg[_L]],f[y-(<<lg[_L])+][lg[_L]]);

 }

 }p,s;

 int a[N1],A[N1],tmp[N1];

 int lower(int l,int r,int *t,int val){

     int ans=-inf,id,mid;

     while(l<=r){

         mid=(l+r)>>;

         if(t[mid]<=val&&t[mid]>ans) ans=t[mid],id=mid,l=mid+;

         else r=mid-;

     }return id;

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     rint i,j;len=n-;

     for(lg[]=,i=;i<=n;i++) lg[i]=lg[i>>]+;

     A[]=gint();

     for(i=;i<=n;i++) A[i]=gint(),a[i-]=tmp[i-]=A[i]-A[i-];

     sort(tmp+,tmp+len+);

     nn=unique(tmp+,tmp+len+)-(tmp+);

     for(i=;i<=len;i++) a[i]=lower(,nn,tmp,a[i]);

     for(i=;i<=len;i++) s.a[i]=a[len-i+],p.a[i]=a[i];

     p.Pre(),s.Pre();

     int lx,rx;ll ans=;

     for(j=;j<=len;j++)

     {

         for(i=;i+j+m<=len;i+=j)

         {

             lx=min(s.query(len-i+,len-(i+j+m)+),j);

             rx=min(p.query(i+,i++j+m),j-);

             ans+=max(,lx+rx-j+);

         }

     }

     printf("%lld\n",ans);

     return ;

 }

 /*

 2 2 2 3 2 1 2 2 2 3 2

 1 2 2 2 3 2

 2

 2 1 2 2 2 3 2

 2 2 2 3 2

 2 2 2 3 2 1 2 2 2 3 2

 2 2 3 2

 2 2 3 2 1 2 2 2 3 2

 2 3 2

 2 3 2 1 2 2 2 3 2

 3 2

 3 2 1 2 2 2 3 2

 2 3 2 2 2 1 2 3 2 2 2

 1 2 3 2 2 2

 2

 2 1 2 3 2 2 2

 2 2

 2 2 1 2 3 2 2 2

 2 2 2

 2 2 2 1 2 3 2 2 2

 2 3 2 2 2

 2 3 2 2 2 1 2 3 2 2 2

 3 2 2 2

 3 2 2 2 1 2 3 2 2 2

 */