又是一道后缀数组题啊。。。
先理清后缀数组如何实现吧,
通过第一关键字,也就是当前$i$的排名$x_i$,来计算出第二关键字$y$,其中$y_i$表示在第二关键字中排名为$i$的编号为$y_i$。
处理的时候倒叙处理其实就是让第一关键字相同的,第二关键字大的先弹出,这里要注意!
还记得$height$数组吗?也就是用来记录排名相近的两个后缀的最长公共长度,有定理:$height[rk[i]]\ge height[rk[i-1]]-1$,具体证明可以参照这里。
如果一次性全部插入,其实答案就是$\frac{n*(n+1)}{2}-\sum\max\{height[rk[i]],height[rk[i]+1]\}$
因此只要统计重复的串的数量减去就好了。
现在是分步插入的话,把串反转之后其实就是多一个后缀$s$。
考虑它的$prv,nxt$,重复贡献变成了$lcp(s,prv)+lcp(s,nxt)-lcp(prv,nxt)$。
只要考虑如何考虑快速计算$lcp$就好了,因为$lcp$具有传递性,用$ST$表搞一下就好了.
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define gc getchar()
#define ll long long
using namespace std;
const int N=1e5+5,Max=1e9,M=1010;
const ll inf=123456789123456789ll;
template<class o>
inline void qr(o &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
template<class o>
void qw(o x)
{
if(x<0)putchar('-'),x=-x;
if(x/10)qw(x/10);
putchar(x%10+48);
}
struct Splay
{
struct node{int f,son[2],d;}t[N];int len,root;
void add(int d,int f){t[++len]=(node){f,{0,0},d};t[f].son[d>t[f].d]=len;}
void rotate(int p,int w)
{
int f=t[p].f,gf=t[f].f;
int r=t[p].son[w],R=f;t[R].son[w^1]=r;if(r)t[r].f=R;
r=p;R=gf;t[R].son[t[R].son[1]==f]=r;t[r].f=R;
r=f;R=p;t[R].son[w]=r;t[r].f=R;
}
void splay(int p,int rt)
{
while(t[p].f!=rt)
{
int f=t[p].f,gf=t[f].f;
if(gf==rt)rotate(p,t[f].son[0]==p);
else
{
if(t[f].son[0]==p&&t[gf].son[0]==f)rotate(f,1),rotate(p,1);
else if(t[f].son[1]==p&&t[gf].son[0]==f)rotate(p,0),rotate(p,1);
else if(t[f].son[0]==p&&t[gf].son[1]==f)rotate(p,1),rotate(p,0);
else rotate(f,0),rotate(p,0);
}
}
if(!rt)root=p;
}
int get_id(int d)
{
int p=root;
while(t[p].d!=d)
{
if(d<t[p].d)
{
if(!t[p].son[0])break;
p=t[p].son[0];
}
if(d>t[p].d)
{
if(!t[p].son[1])break;
p=t[p].son[1];
}
}
return p;
}
void ins(int d)
{
if(!root){add(d,0);root=len;return ;}
int p=get_id(d);add(d,p);splay(len,0);
}
void del(int d)
{
int p=get_id(d);splay(p,0);
if(!t[p].son[0]&&!t[p].son[1])root=0,len=0;
else if(t[p].son[1]&&!t[p].son[0])t[root=t[p].son[1]].f=0;
else if(t[p].son[0]&&!t[p].son[1])t[root=t[p].son[0]].f=0;
else
{
int R=t[p].son[0];while(t[R].son[1])R=t[R].son[1];splay(R,p);
int r=t[p].son[1];t[R].son[1]=r;t[r].f=R;t[root=R].f=0;splay(R,0);
}
}
int nxt(int d)
{
int p=get_id(d);splay(p,0);
if(t[p].d<=d&&t[p].son[1])
for(p=t[p].son[1];t[p].son[0];p=t[p].son[0]);
if(t[p].d<=d)return -1;
return t[p].d;
}
int prv(int d)
{
int p=get_id(d);splay(p,0);
if(t[p].d>=d&&t[p].son[0])
for(p=t[p].son[0];t[p].son[1];p=t[p].son[1]);
if(t[p].d>=d)return -1;
return t[p].d;
}
}spl;
int a[N],n,m,sa[N],wa[N],wb[N],wv[N],height[N],c[N],rk[N];
bool same(int *x,int a,int b,int l){return x[a]==x[b]&&x[a+l]==x[b+l];}
void SA()
{
int *x=wa,*y=wb,*t;
for(int i=1;i<=n;i++)++c[x[i]=a[i]];
for(int i=2;i<=m;i++)c[i]+=c[i-1];
for(int i=n;i;i--)sa[c[x[i]]--]=i;
for(int j=1,p=0;p<n;j<<=1,m=p)
{
p=0;for(int i=n-j+1;i<=n;i++)y[++p]=i;
for(int i=1;i<=n;i++)if(sa[i]>j)y[++p]=sa[i]-j;
for(int i=1;i<=m;i++)c[i]=0;
for(int i=1;i<=n;i++)++c[wv[i]=x[y[i]]];
for(int i=2;i<=m;i++)c[i]+=c[i-1];
for(int i=n;i;i--)sa[c[wv[i]]--]=y[i];
p=1;t=x;x=y;y=t;x[sa[1]]=1;
for(int i=2;i<=n;i++)
x[sa[i]]=same(y,sa[i],sa[i-1],j)?p:++p;
}
for(int i=1;i<=n;i++)rk[sa[i]]=i;
for(int i=1,j,k=0;i<=n;height[rk[i++]]=k)
for(k?--k:0,j=sa[rk[i]-1];a[j+k]==a[i+k];++k);
}
int f[N][18],Log[N];
void ST()
{
for(int i=1;i<n;i++)f[i][0]=height[i+1];
for(int i=2;i<n;i++)Log[i]=Log[i>>1]+1;
for(int t=1;t<=17;t++)
for(int i=1;i+(1<<t)<=n;i++)
f[i][t]=min(f[i][t-1],f[i+(1<<(t-1))][t-1]);
}
int arr[N],len;
inline int lcp(int x,int y)
{
if(x>y)swap(x,y);
int t=Log[y-x];return min(f[x][t],f[y-(1<<t)][t]);
}
inline int get(int d)
{
int l=1,r=len;
while(l<r)
{
int mid=l+r>>1;
if(arr[mid]<d)l=mid+1;
else r=mid;
}
return l;
}
int main()
{
//freopen("incantation3.in","r",stdin);
//freopen("incantation3.ans","w",stdout);
qr(n);
for(int i=n;i;i--)qr(a[i]),arr[i]=a[i];
sort(arr+1,arr+n+1);
for(int i=1;i<=n;i++)if(i==1||arr[i]!=arr[i-1])arr[++len]=arr[i];
for(int i=1;i<=n;i++)a[i]=get(a[i]);ll cnt=0;
m=1e5;SA();ST();
for(int i=n;i;i--)
{
int prv=spl.prv(rk[i]),nxt=spl.nxt(rk[i]);
if(prv!=-1&&nxt!=-1)cnt+=lcp(prv,nxt);
if(prv!=-1)cnt-=lcp(prv,rk[i]);
if(nxt!=-1)cnt-=lcp(rk[i],nxt);
spl.ins(rk[i]);cnt+=n-i+1;qw(cnt);puts("");
}
return 0;
}
最后一次更新于2020-03-21
0 条评论