bzoj 4650(洛谷 1117) [Noi2016]优秀的拆分——枚举长度的关键点+后缀数组

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4650

　　　https://www.luogu.org/problemnew/show/P1117

和 bzoj2119 股市的预测一样。

考虑算出每个点往前的 AA 的个数和往后的 BB 的个数，每个点作为 AA 和 BB 分界点的答案累加起来就行。

算一个点开始的 AA 的个数，就是枚举 A 的长度 L ，然后每 L 个分为一段，在段的开头求 LCP 和 LCS ，给合法的位置区间加1就行。

一开始写成 n² 了，还能有 95 分。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

int Mn(int a,int b){return a<b?a:b;}

int Mx(int a,int b){return a>b?a:b;}

const int N=6e4+,K=;

int T,n,len,sa[N],rk[N],tp[N],tx[N],ht[N][K],lg[N],bin[K];

int s[N],f[N],g[N]; char ch[N];

void Rsort(int n,int nm)

{

  for(int i=;i<=nm;i++)tx[i]=;

  for(int i=;i<=n;i++)tx[rk[i]]++;

  for(int i=;i<=nm;i++)tx[i]+=tx[i-];

  for(int i=n;i;i--)sa[tx[rk[tp[i]]]--]=tp[i];

}

void get_sa(int n)

{

  int nm=;

  for(int i=;i<=n;i++)tp[i]=i,rk[i]=s[i]+;

  Rsort(n,nm);

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

    {

      int tot=;

      for(int i=n-k+;i<=n;i++)tp[++tot]=i;

      for(int i=;i<=n;i++)

    if(sa[i]>k)tp[++tot]=sa[i]-k;

      Rsort(n,nm);memcpy(tp,rk,sizeof rk);

      nm=; rk[sa[]]=;

      for(int i=;i<=n;i++)

    {

      int u=sa[i]+k,v=sa[i-]+k; if(u>n)u=;if(v>n)v=;

      rk[sa[i]]=(tp[sa[i]]==tp[sa[i-]]&&tp[u]==tp[v])?nm:++nm;

    }

      if(nm==n)break;

    }

}

void ht_init(int n)

{

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

  bin[]=;for(int i=;i<=lg[n];i++)bin[i]=bin[i-]<<;

}

void get_ht(int n)

{

  for(int i=,k=,j;i<=n;i++)

    {

      for((k?k--:),j=sa[rk[i]-];i+k<=n&&j+k<=n&&s[i+k]==s[j+k];k++);

      ht[rk[i]][]=k;

    }

  for(int t=;t<=lg[n];t++)

    for(int i=;i+bin[t]-<=n;i++)

      ht[i][t]=Mn(ht[i][t-],ht[i+bin[t-]][t-]);

}

int qry_ht(int l,int r,bool fx)

{

  if(l==r)return fx?sa[l]-n-:n-sa[l]+;

  if(l>r)swap(l,r); int d=lg[r-l];

  return Mn(ht[l+][d],ht[r-bin[d]+][d]);

}

void add(int x,int k,int *f){for(;x<=len;x+=(x&-x))f[x]+=k;}

int qry(int x,int *f){int ret=;for(;x;x-=(x&-x))ret+=f[x];return ret;}

int main()

{

  scanf("%d",&T); ht_init(); s[]=;

  while(T--)

    {

      scanf("%s",ch+);

      n=strlen(ch+); len=n*+;

      for(int i=,j=len;i<=n;i++,j--)s[i]=s[j]=ch[i]-'a'+;

      s[n+]=; get_sa(len); get_ht(len);

      memset(f,,sizeof f); memset(g,,sizeof g);

      for(int L=,lm=n>>,lst=,tmp=L<<;L<=lm;L++,lst=,tmp+=)

    for(int i=;i+L<=n;i+=L)

      {

        int l2=qry_ht(rk[i],rk[i+L],);

        int l1=qry_ht(rk[len-i+],rk[len-i-L+],);

        int st=Mx(lst+,i-l1+);

        int en=i+l2-L;

        if(en<st)continue; lst=en;

        add(st,,f); add(en+,-,f);

        add(st+tmp-,,g); add(en+tmp,-,g);

      }

      ll ans=;

      for(int i=;i<n;i++)

    ans+=(ll)qry(i,g)*qry(i+,f);

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

    }

  return ;

}