cogs2223 [SDOI2016 Round1] 生成魔咒

cogs2223 [SDOI2016 Round1] 生成魔咒

---

原题链接

---

题解

暴力：每次更新后缀数组？？？
set+二分+hash暴力 http://paste.ubuntu.com/25496298/
正解：把串反过来，答案不变，但每次只需插入一个后缀。
先预处理出整个后缀数组，然后set插入。
len=n时，\(ans=\frac{n(n+1)}{2}-\sum ht[i]\)

---

Code

// It is made by XZZ
#include<cstdio>
#include<algorithm>
#include<set>
#include<cmath>
#define Fname "magic"
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
#define mp make_pair
#define pr pair<unsigned int,ll>
typedef long long ll;
il int gi(){
    rg int x=0;rg char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x;
}
const int maxn=600100;
int c[maxn],data[maxn],n,tot;
struct node{int l;};
il node Make(int a){return(node){a};}
set<node>s;
int sa[maxn],rk[maxn],tmp[maxn],buc[maxn],m,ht[maxn],st[maxn][19];
il vd Qsort(){
    rep(i,0,m)buc[i]=0;
    rep(i,1,n)buc[rk[tmp[i]]]++;
    rep(i,1,m)buc[i]+=buc[i-1];
    drep(i,n,1)sa[buc[rk[tmp[i]]]--]=tmp[i];
}
il bool cmp(int*h,int a,int b,int l){return h[a]==h[b]&&h[a+l]==h[b+l];}
il vd solve(){
    m=tot;
    rep(i,1,n)rk[i]=c[i],tmp[i]=i;
    Qsort();
    int p=0;
    for(rg int l=1;p<n;l<<=1){
    p=0;
    rep(i,n-l+1,n)tmp[++p]=i;
    rep(i,1,n)if(sa[i]>l)tmp[++p]=sa[i]-l;
    Qsort();
    rep(i,1,n)tmp[i]=rk[i];
    p=rk[sa[1]]=1;
    rep(i,2,n)
        if(cmp(tmp,sa[i],sa[i-1],l))rk[sa[i]]=p;
        else rk[sa[i]]=++p;
    m=p;
    }
    p=0;
    rep(i,1,n)sa[rk[i]]=i;
    rep(i,1,n){
    if(p)--p;
    if(rk[i]==n)continue;
    while(c[i+p]==c[sa[rk[i]+1]+p])++p;
    ht[rk[i]]=st[rk[i]][0]=p;
    }
    int Log=log2(n);
    rep(i,1,Log)drep(j,n-(1<<i)+1,1)st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
bool operator <(node AAA,node BBB){return rk[AAA.l]<rk[BBB.l];}
il int lcp(int a,int b){
    a=rk[a],b=rk[b];
    if(a==b)return n-a+1;
    if(a>b)swap(a,b);--b;
    int Log=log2(b-a+1);
    return min(st[a][Log],st[b-(1<<Log)+1][Log]);
}
int main(){
    freopen(Fname".in","r",stdin);
    freopen(Fname".out","w",stdout);
    n=gi();
    rep(i,1,n)c[n-i+1]=data[n-i+1]=gi();c[n+1]=-23333333;
    sort(data+1,data+1+n);
    tot=unique(data+1,data+1+n)-data-1;
    rep(i,1,n)c[i]=lower_bound(data+1,data+tot+1,c[i])-data;
    solve();
    puts("1"),s.insert(Make(n));
    ll ht=0;
    set<node>::iterator it,itl,itr;
    drep(i,n-1,1){
    it=s.insert(Make(i)).first;
    itl=it,--itl;
    itr=it,++itr;
    if(it==s.begin())ht+=lcp(it->l,itr->l);
    else if(itr==s.end())ht+=lcp(itl->l,it->l);
    else ht+=lcp(it->l,itr->l)+lcp(itl->l,it->l)-lcp(itl->l,itr->l);
    printf("%lld\n",(ll)(n-i+1)*(n-i+2)/2-ht);
    }
    return 0;
}