渐渐感觉到省选难度的天差地别
题解：
前60是送给暴力的？
后面40分
首先其子串个数就不是能统计范围内的，所以hash或者trie已经挂了
那么就剩下后缀数组和自动机了（我不会啊）
考虑一下后缀数组。。
后缀数组原本答案等于总的子串-sigma(height[i])
它每一次都是在末尾加入，其实也就是增加了一个前缀
所以 就可以改成一个前缀数组（其实就是把串翻转一下）
然后 其实就非常简单了。。
我们可以先把整个串的height搞出来
然后插入一个元素实际就是插入一个后缀
那么查找到它的前一个后缀和后一个后缀，用rmq查找他们之间的lcp
前驱后继显然是用splay维护的（因为不会set）
考前模板题。。
代码：
#include <bits/stdc++.h> using namespace std; #define ll long long #define N 110000 #define INF 5e8 ll sa[N],a[N],c[N],x[N],y[N],rank[N],height[N],ans2[N]; ll num2,root,n,m,bz[N][21],fa[N],leftson[N],rightson[N],data[N]; struct re{ ll a,b; }cc[N]; void get_sa(ll n,ll m) { ll p=0,f=0; for (ll i=1;i<=m;i++) c[i]=0; for (ll i=1;i<=n;i++) c[x[i]=a[i]]++; for (ll i=1;i<=m;i++) c[i]+=c[i-1]; for (ll i=n;i;i--) sa[c[x[i]]--]=i; for (ll i=1;i<=n&&p<=n;i<<=1) { p=0; for (ll j=n-i+1;j<=n;j++) y[++p]=j; for (ll j=1;j<=n;j++) if (sa[j]>i) y[++p]=sa[j]-i; for (ll j=1;j<=m;j++) c[j]=0; for (ll j=1;j<=n;j++) c[x[y[j]]]++; for (ll j=1;j<=m;j++) c[j]+=c[j-1]; for (ll j=n;j;j--) sa[c[x[y[j]]]--]=y[j]; swap(x,y); x[sa[1]]=1; p=2; for (ll j=2;j<=n;j++) x[sa[j]]=y[sa[j]]==y[sa[j-1]]&&y[sa[j]+i]==y[sa[j-1]+i] ?p-1:p++; m=p; } for (ll i=1;i<=n;i++) rank[sa[i]]=i; for (ll i=1;i<=n;i++) { ll j=sa[rank[i]-1]; if (f) f--; while (a[i+f]==a[j+f]) f++; height[rank[i]]=f; } for (ll i=1;i<=n;i++) bz[i][0]=height[i]; for (ll i=1;i<=20;i++) for (ll j=1;j<=n;j++) if (j+(1<<i)-1<=n) bz[j][i]=min(bz[j][i-1],bz[j+(1<<(i-1))][i-1]); } ll lcp(ll a,ll b) { ll x=rank[a],y=rank[b]; if (x>y) swap(x,y); x++; ll z=log2(y-x+1); return (min(bz[x][z],bz[y-(1<<z)+1][z])); } void rotate(ll x,ll y) { ll father=fa[x]; if (y==1) { rightson[father]=leftson[x]; if (leftson[x]) fa[leftson[x]]=father; } else { leftson[father]=rightson[x]; if (rightson[x]) fa[rightson[x]]=father; } fa[x]=fa[father]; if (fa[x]) { if (leftson[fa[x]]==father) leftson[fa[x]]=x; else rightson[fa[x]]=x; } fa[father]=x; if (y==1) leftson[x]=father; else rightson[x]=father; //updata(father); updata(x); } void splay(ll x,ll goal) { if (x==root) return; ll father=fa[x]; while (father!=goal) { if (fa[father]==goal) { if (x==leftson[father]) rotate(x,2); else rotate(x,1); } else { if (leftson[fa[father]]==father) if (leftson[father]==x) rotate(father,2),rotate(x,2); else rotate(x,1),rotate(x,2); else if (rightson[father]==x) rotate(father,1),rotate(x,1); else rotate(x,2),rotate(x,1); } father=fa[x]; } if (goal==0) root=x; } void insert(ll x) { ll y=root; while (y) { //count2[y]++; if (x<data[y]) { if (!leftson[y]) break; y=leftson[y]; } else { if (!rightson[y]) break; y=rightson[y]; } } data[++num2]=x; fa[num2]=y; if (x>data[y]) rightson[y]=num2; else leftson[y]=num2; splay(num2,0); } ll pre(ll x) { ll y=root,maxn=-INF; while (y) { if (data[y]<=x) maxn=max(maxn,data[y]); if (data[y]<=x) y=rightson[y]; else y=leftson[y]; } return maxn; } ll succ(ll x) { ll y=root,minn=INF; while (y) { if (data[y]>=x) minn=min(minn,data[y]); if (data[y]<=x) y=rightson[y]; else y=leftson[y]; } return minn; } bool cmp(re x,re y) { return(x.a<y.a); } int main() { cin>>n; for (ll i=1;i<=n;i++) { cin>>cc[i].a; cc[i].b=n-i+1; } sort(cc+1,cc+n+1,cmp); cc[0].a=-INF; ll sum=0; for (ll i=1;i<=n;i++) { if (cc[i].a!=cc[i-1].a) sum++; a[cc[i].b]=sum; } get_sa(n,n); ll ans=0; for (ll i=1;i<=n;i++) { ll x=n-i+1; ll x1=pre(rank[x]),x2=succ(rank[x]); if (x1!=-INF) x1=sa[x1],ans+=ans2[x]=lcp(x1,x); if (x2!=INF) x2=sa[x2],ans-=ans2[x2],ans+=ans2[x2]=lcp(x,x2); cout<<i*(i+1)/2-ans<<endl; insert(rank[x]); } return 0; }