题目描述
魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符 1、2 拼凑起来形成一个魔咒串 [1,2]。
一个魔咒串 S 的非空字串被称为魔咒串 S 的生成魔咒。
例如 S=[1,2,1] 时，它的生成魔咒有 [1]、[2]、[1,2]、[2,1]、[1,2,1] 五种。S=[1,1,1] 时，它的生成魔咒有 [1]、[1,1]、[1,1,1] 三种。最初 S 为空串。共进行 n 次操作，每次操作是在 S 的结尾加入一个魔咒字符。每次操作后都需要求出，当前的魔咒串 S 共有多少种生成魔咒。
输入输出格式
输入格式：
第一行一个整数 n。
第二行 n 个数，第 i 个数表示第 i 次操作加入的魔咒字符。
输出格式：
输出 n 行，每行一个数。第 i 行的数表示第 i 次操作后 S 的生成魔咒数量
输入输出样例
说明
对于%10的数据，1≤n≤101 \le n \le 101≤n≤10
对于%30的数据，1≤n≤1001 \le n \le 1001≤n≤100
对于%60的数据，1≤n≤1001 \le n \le 1001≤n≤100
对于%100的数据，1≤n≤1000001 \le n \le 1000001≤n≤100000
用来表示魔咒字符的数字 x 满足1≤n≤1091 \le n \le 10^91≤n≤109
反转字符串，这样就变成了后缀
先后缀数组求出height数组
然后从前往后一个一个加
首先我们知道一个字符串的字串数是每个后缀的长度减去height[i]
每加入一个字符，就新产生一个后缀
那么每添加一个前缀，增加了多少个不同的子串，其实就是在之前添加的前缀中
排名最靠近该前缀的两个串a和b，计算出他们与该前缀的lcp，
然后不同的子串数就是当前添加的前缀长度len-max(lcpa,lcpb)了
找排名最靠近的用线段树
以后模板改了，从1开始，方便很多
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<set>
using namespace std;
typedef long long lol;
int n,m,c[],x[],y[],SA[],s[],b[],rank[],h[];
int Mx[],Mi[],Log[],Min[][];
lol ans;
void radix_sort()
{int i;
for (i=;i<=m;i++)
c[i]=;
for (i=;i<=n;i++)
c[x[y[i]]]++;
for (i=;i<=m;i++)
c[i]+=c[i-];
for (i=n;i>=;i--)
SA[c[x[y[i]]]--]=y[i];
}
void build_SA()
{int i,j,k,p;
for (i=;i<=n;i++)
x[i]=s[i],y[i]=i;
m=;
radix_sort();
for (k=;k<=n;k<<=)
{
p=;
for (i=n-k+;i<=n;i++)
y[++p]=i;
for (i=;i<=n;i++)
if (SA[i]>k) y[++p]=SA[i]-k;
radix_sort();
p=;swap(x,y);
x[SA[]]=;
for (i=;i<=n;i++)
x[SA[i]]=((y[SA[i]]==y[SA[i-]])&&(y[SA[i]+k]==y[SA[i-]+k]))?p:++p;
if (p>=n) break;
m=p;
}
for (i=;i<=n;i++)
rank[SA[i]]=i;
int L=;
for (i=;i<=n;i++)
{
if (L>) L--;
j=SA[rank[i]-];
while (i+L<=n&&j+L<=n&&(s[j+L]==s[i+L])) L++;
h[rank[i]]=L;
}
}
void update(int rt,int l,int r,int x)
{
if (l==r)
{
Mx[rt]=Mi[rt]=x;
return;
}
int mid=(l+r)/;
if (x<=mid) update(rt<<,l,mid,x);
else update(rt<<|,mid+,r,x);
Mx[rt]=max(Mx[rt<<],Mx[rt<<|]);
Mi[rt]=min(Mi[rt<<],Mi[rt<<|]);
}
int query(int rt,int l,int r,int L,int R,int p)
{
if (l>=L&&r<=R)
{
if (p==)
return Mx[rt];
else return Mi[rt];
}
int mid=(l+r)/,mx=,mi=n+;
if (p==)
{
if (L<=mid) mx=max(mx,query(rt<<,l,mid,L,R,p));
if (R>mid) mx=max(mx,query(rt<<|,mid+,r,L,R,p));
return mx;
}
else
{
if (L<=mid) mi=min(mi,query(rt<<,l,mid,L,R,p));
if (R>mid) mi=min(mi,query(rt<<|,mid+,r,L,R,p));
return mi;
}
}
int RMQ(int x,int y)
{
int L=Log[y-x+];
return min(Min[x][L],Min[y-(<<L)+][L]);
}
int main()
{int i,tot,j,tmp;
//freopen("zyys.out","w",stdout);
scanf("%d",&n);
for (i=;i<=n;i++)
{
scanf("%d",&s[n-i+]);
b[i]=s[n-i+];
}
sort(b+,b+n+);
tot=unique(b+,b+n+)-b-;
for (i=;i<=n;i++)
s[i]=lower_bound(b+,b+tot+,s[i])-b;
build_SA();
Log[]=;
for (i=;i<=n;i++)
Log[i]=Log[i/]+;
for (i=;i<=n;i++)
Min[i][]=h[i];
for (j=;(<<j)<=n;j++)
{
for (i=;i<=n-(<<j)+;i++)
Min[i][j]=min(Min[i][j-],Min[i+(<<j-)][j-]);
}
memset(Mx,-/,sizeof(Mx));memset(Mi,/,sizeof(Mi));
update(,,n+,);update(,,n+,n+);
for (i=n;i>=;i--)
{
int now=rank[i];
int pre=query(,,n+,,now-,),nxt=query(,,n+,now+,n+,);
tmp=;
if (pre>=)
tmp=max(tmp,RMQ(pre+,now));
if (nxt<=n)
tmp=max(tmp,RMQ(now+,nxt));
ans+=n-i+-tmp;
printf("%lld\n",ans);
update(,,n+,now);
}
}