【SDOI2016】生成魔咒

题面

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

题解

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
#define ri register int
#define N 100050
using namespace std;

int n;
int a[N];

struct SAM {
  int ff[N<<1],len[N<<1];
  map<int,int> ch[N<<1];
  int las,tot;
  long long ret;
  void init() {
    las=tot=1;
    ret=0;
  }
  void extend(int c) {
    int np=++tot,p=las; las=np;
    len[np]=len[p]+1;
    while (p && !ch[p][c]) ch[p][c]=np,p=ff[p];
    if (!p) ff[np]=1;
    else {
      int q=ch[p][c];
      if (len[q]==len[p]+1) ff[np]=q;
      else {
        int nq=++tot;
        ch[nq]=ch[q]; ff[nq]=ff[q];
        len[nq]=len[p]+1; ret+=(len[nq]-len[ff[nq]]);
        ret-=(len[q]-len[ff[q]]);
        ff[np]=ff[q]=nq;
        ret+=(len[q]-len[ff[q]]);
        while (p && ch[p][c]==q) ch[p][c]=nq,p=ff[p];
      }
    }
    ret+=len[np]-len[ff[np]];
  }
} sam;

int main(){
  scanf("%d",&n);
  for (ri i=1;i<=n;i++) scanf("%d",&a[i]);
  sam.init();
  for (ri i=1;i<=n;i++) {
    sam.extend(a[i]);
    printf("%lld
",sam.ret);
  }
}