【AHOI2013】差异（2）

题面

https://www.luogu.org/problem/P4248

题解

这里，提供后缀数组的做法。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
const int N=1000050;
using namespace std;
char s[N];
int n,m,rank[N],sa[N],tax[N],tp[N],height[N];
struct rmq {
  int minh,loc;
} r[N][25];
long long sum[N];
long long ans=0;

void cntsort(){
  for (int i=0;i<=m;i++) tax[i]=0;
  for (int i=1;i<=n;i++) tax[rank[i]]++;
  for (int i=1;i<=m;i++) tax[i]+=tax[i-1];
  for (int i=n;i>=1;i--) sa[tax[rank[tp[i]]]--]=tp[i];
}

void suffixsort(){
  m=75;
  for (int i=1;i<=n;i++) rank[i]=s[i]-‘0‘+1,tp[i]=i;
  cntsort();
  for (int w=1,p=0;p<n;m=p,w<<=1) {
    p=0;
    for (int i=1;i<=w;i++) tp[++p]=n-w+i;
    for (int i=1;i<=n;i++) if (sa[i]>w) tp[++p]=sa[i]-w;
    cntsort();
    swap(tp,rank);
    rank[sa[1]]=p=1;
    for (int i=2;i<=n;i++) 
      rank[sa[i]]=(tp[sa[i-1]]==tp[sa[i]] && tp[sa[i-1]+w]==tp[sa[i]+w]) ? p:++p;
  }
}
void getheight(){
  int k=0;
  for (int i=1;i<=n;i++) {
    if (k) k--;
    int j=sa[rank[i]-1];
    while (s[i+k]==s[j+k]) k++;
    height[rank[i]]=k;
  }
}

void getsum(){
  int i;
  sum[0]=0;
  for (i=1;i<=n;i++) sum[i]=sum[i-1]+n-sa[i]+1;
}

void getrmq(){
  int i,j;
  for (i=1;i<=n;i++) r[i][0]=(rmq){height[i],i};
  for (i=1;i<=20;i++) {
    int l=(1<<i);
    for (j=1;j<=n;j++) if (r[j][i-1].minh<r[j+l/2][i-1].minh) r[j][i]=r[j][i-1]; else r[j][i]=r[j+l/2][i-1];
  }
}

void solve(int L,int R){
  int i,minh=0x7f7f7f7f,p,mid=L+R>>1;
  int len=1,cnt=0;
  while (len<=R-L+1) len*=2,cnt++;
  len/=2; cnt--;
  rmq r1=r[L][cnt],r2=r[R-len+1][cnt];
  if (r1.minh<r2.minh) {
      p=r1.loc;
      minh=r1.minh;
  }
  else {
      p=r2.loc;
      minh=r2.minh;
  }
  long long sum1=sum[p-1]-sum[L-2],sum2=sum[R]-sum[p-1];
  ans+=sum1*(R-p+1)+sum2*(p-L+1)-2*(R-p+1)*1LL*(p-L+1)*minh;
  if (L<=p-1) solve(L,p-1);
  if (p+1<=R) solve(p+1,R);
}

int main(){
  scanf("%s",s+1);
  n=strlen(s+1);
  suffixsort();
  getheight();
  getsum();
  getrmq();
  solve(2,n);
  cout<<ans<<endl;
  return 0;
}