正題

題目鏈接:https://www.luogu.com.cn/problem/P4070

---

題目大意

長度為$n$的字符串，對于每個$i$求字符串$1～i$部分有多少個不同的子串。

---

解題思路

對于整個串$ans={\sum }_{i=1}^{n}n?i+1?heigh{t}_i$，考慮如何維護$height$
往末尾加上一個字符會對$height$造成很大影響，但是如果在字符串前面加上一個$height$的話就不會對其他$height$造成影響了。

所以先翻轉字符串，問題變為每次在前面加上一個字符。

首先離線后綴排好序，然后每次加入一個字符時，我們用平衡樹找已經插入的前驅和后繼然后用$ST$表來求到他們的$LCP$（也就是更新后的$height$）即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<set> using namespace std; const int N=1e5+10; int n,m,a[N],b[N],height[N],lg[N]; int c[N],sa[N],rk[N],x[N],y[N]; int f[20][N];long long ans; set<int> s; void Qsort(){for(int i=1;i<=m;i++)c[i]=0;for(int i=1;i<=n;i++)c[x[i]]++;for(int i=1;i<=m;i++)c[i]+=c[i-1];for(int i=n;i>=1;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0;return; } void SA(){for(int i=1;i<=n;i++)x[i]=a[i],y[i]=i;Qsort();for(int w=1;w<=n;w<<=1){int p=0;for(int i=n-w+1;i<=n;i++)y[++p]=i;for(int i=1;i<=n;i++)if(sa[i]>w)y[++p]=sa[i]-w;Qsort();swap(x,y);p=x[sa[1]]=1;for(int i=2;i<=n;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+w]==y[sa[i-1]+w])?p:++p;if(p==n)break;m=p;}return; } void Get_Height(){int k=0;for(int i=1;i<=n;i++)rk[sa[i]]=i;for(int i=1;i<=n;i++){if(rk[i]==1)continue;if(k)k--;int j=sa[rk[i]-1];while(i+k<=n&&j+k<=n&&a[i+k]==a[j+k])k++;height[rk[i]]=k;}return; } void RMQ(){lg[0]=-1;for(int i=1;i<=n;i++)lg[i]=lg[i/2]+1,f[0][i]=height[i];for(int i=1;i<19;i++)for(int j=1;j+(1<<i-1)<=n;j++)f[i][j]=min(f[i-1][j],f[i-1][j+(1<<i-1)]);return; } int LCP(int l,int r){l++;int z=lg[r-l+1];return min(f[z][l],f[z][r+1-(1<<z)]); } int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=a[i];}sort(b+1,b+1+n);m=unique(b+1,b+1+n)-b-1;for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+m,a[i])-b;for(int i=1;i<=n/2;i++)swap(a[i],a[n-i+1]);SA();Get_Height();RMQ();for(int i=n;i>=1;i--){s.insert(rk[i]);set<int>::iterator it=s.find(rk[i]);int k=0;if(it!=s.begin()){int p=*(--it);k=LCP(p,rk[i]);++it;}++it;if(it!=s.end()){int p=*it;k=max(k,LCP(rk[i],p));}ans+=n-i+1-k;printf("%lld\n",ans);} } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的P4070-[SDOI2016]生成魔咒【SA,平衡树】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。