fAKeT又来骗流量了（好像以前也没骗到
后缀数组好难啊。。。。。。
推荐博客：%%%DeepinC 这篇讲解除了太过详细以外都挺好
然后照例放题解包。
裸考后缀数组的题很少，大部分的题都是用后缀数组求出height数组，然后再结合各种各样的数据结构。
以下将height简称为h
相似子串
还是稍裸的。。。
给定两个本质不同子串的排名，求他们的公共前缀和公共后缀。
首先要根据排名求出子串。
因为要本质不同，所以对于sa[i]，它与sa[i-1]的公共部分，即h[i]，对子串个数不作贡献，只有长度大于h[i]的部分作出贡献
所以单点的贡献可以用后缀长度减去对应的h求得
然后对其求前缀和，查询时lower_bound即可得到对应字串的起点，用rank减去（起点-1）的前缀和，在加上起点的h即可得到串长
因为要前后分别统计，将串reverse一下在跑一遍sa即可。统计时可以用st表
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 #define N 200050 5 int n,m; 6 int bin[30],lg2[N]; 7 inline void init(int n){ 8 for(int i=0;i<=20;++i)bin[i]=1<<i; 9 for(int i=2;i<=n;++i)lg2[i]=lg2[i>>1]+1; 10 } 11 #define mmp make_pair 12 #define fir first 13 #define sec second 14 struct SA{ 15 char s[N]; 16 int sa[N],rk[N],h[N],st[N][18]; 17 LL h2[N]; 18 inline void getsa(int m){ 19 int t1[N],t2[N],t3[N],*x=t1,*y=t2,*c=t3; 20 memset(c,0,sizeof(int)*(m+1)); 21 for(int i=1;i<=n;++i)c[x[i]=s[i]-'a'+1]++; 22 for(int i=1;i<=m;++i)c[i]+=c[i-1]; 23 for(int i=1;i<=n;++i)sa[c[x[i]]--]=i; 24 if(m==n)++m; 25 for(int len=1;len<=n&&(m^n);len<<=1){ 26 int num=0; 27 for(int i=n-len+1;i<=n;++i)y[++num]=i; 28 for(int i=1;i<=n;++i)if(sa[i]>len)y[++num]=sa[i]-len; 29 memset(c,0,sizeof(int)*(m+1)); 30 for(int i=1;i<=n;++i)++c[x[i]]; 31 for(int i=1;i<=m;++i)c[i]+=c[i-1]; 32 for(int i=n;i;--i)sa[c[x[y[i]]]--]=y[i]; 33 swap(x,y); 34 memset(x,0,sizeof(int)*(n+1)); 35 x[sa[1]]=1;m=1; 36 for(int i=2;i<=n;++i) 37 x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+len]==y[sa[i-1]+len])?m:++m; 38 } 39 for(int i=1;i<=n;++i)rk[sa[i]]=i; 40 } 41 inline void geth(){ 42 for(int i=1,k=0;i<=n;h[rk[i++]]=k,k=k?k-1:0) 43 while(s[i+k]==s[sa[rk[i]-1]+k])++k; 44 for(int i=1;i<=n;++i)h2[i]=h2[i-1]+n-sa[i]+1-h[i]; 45 } 46 inline void getst(){ 47 for(int i=1;i<=n;++i)st[i][0]=h[i]; 48 for(int j=1;j<=lg2[n];++j) 49 for(int i=1;i<=n;++i) 50 st[i][j]=min(st[i][j-1],st[i+bin[j-1]][j-1]); 51 } 52 inline int ask(int l,int r){ 53 if(l>r)swap(l,r); 54 // cout<<l<<" "<<r<<endl; 55 if(l==r)return n-sa[l]+1; 56 return min(st[l+1][lg2[r-l]],st[r-bin[lg2[r-l]]+1][lg2[r-l]]); 57 } 58 inline pair<int,int> getpos(LL rank){ 59 int t=upper_bound(h2+1,h2+n+1,rank-1)-h2; 60 return mmp(sa[t],h[t]+rank-h2[t-1]); 61 } 62 }t1,t2; 63 int main(){ 64 // freopen("da.in","r",stdin); 65 //freopen("my.out","w",stdout); 66 scanf("%d%d",&n,&m); 67 scanf("%s",t1.s+1); 68 for(int i=1;i<=n;++i)t2.s[i]=t1.s[i]; 69 reverse(t2.s+1,t2.s+n+1); 70 init(n); 71 t1.getsa(27);t1.geth();t1.getst(); 72 t2.getsa(27);t2.geth();t2.getst(); 73 //cout<<t1.h2[n]<<endl; 74 //for(int i=1;i<=n;++i)cout<<t1.sa[i]<<" "<<t1.h[i]<<" "<<t1.h2[i]<<endl; 75 LL r1,r2; 76 //cout<<"rk1:"<<t1.rk[1]<<endl; 77 //for(int i=1;i<=t1.h2[n];++i){ 78 // pair<int,int>x=t1.getpos(i); 79 // printf("%d %d ",x.fir,x.sec); 80 //} 81 for(int i=1,p1,p2;i<=m;++i){ 82 pair<int,int>x,y; 83 scanf("%lld%lld",&r1,&r2); 84 if(r2>t1.h2[n]){puts("-1");continue;} 85 x=t1.getpos(r1);y=t1.getpos(r2); 86 // printf("x:%d %d ",x.fir,x.sec); 87 // printf("y:%d %d ",y.fir,y.sec); 88 int mi=min(x.sec,y.sec); 89 p1=t1.ask(t1.rk[x.fir],t1.rk[y.fir]); 90 if(mi<p1)p1=mi; 91 x.fir=n-(x.fir+x.sec-1)+1; 92 y.fir=n-(y.fir+y.sec-1)+1; 93 // printf("x2:%d %d ",x.fir,x.sec); 94 // printf("y2:%d %d ",y.fir,y.sec); 95 p2=t2.ask(t2.rk[x.fir],t2.rk[y.fir]); 96 //cout<<p2<<endl; 97 if(mi<p2)p2=mi; 98 // cout<<p1<<p2<<endl; 99 printf("%lld ",1ll*p1*p1+1ll*p2*p2); 100 } 101 }
品酒大会
NOI2015的题。sa+单调栈+st表
先跑sa，求出h数组
考虑用单调栈求出每个点的h作为区间最小值的区间
那么这个区间（最小值的位置为x）对数量的贡献为x左区间的长度*x右区间的长度。
对最值的贡献为x左区间的最大值*x右区间的最大值与x左区间的最小值*x右区间的最小值，二者取max
最后倒扫一遍传递贡献即可。记得开long long
如果你看不懂上面这一段就当我yasei
还是详细点吧。
首先我的数组下标是基于后缀的排名的，即下标为排名
同时下标也是h的下标。是不是好理解一点了？
然后就没有然后了，然后就上代码了。
1 #include<bits/stdc++.h> 2 #define N 600050 3 #define LL long long 4 namespace ae86{ 5 const int bufl=1<<15; 6 char buf[bufl],*s=buf,*t=buf; 7 inline int fetch(){ 8 if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;} 9 return*s++; 10 } 11 inline int read(){ 12 int a=0,b=1,c=fetch(); 13 while(!isdigit(c))b^=c=='-',c=fetch(); 14 while(isdigit(c))a=a*10+c-48,c=fetch(); 15 return b?a:-a; 16 } 17 } 18 using ae86::read; 19 using namespace std; 20 int n; 21 int a[N]; 22 char s[N]; 23 int sa[N],rk[N],h[N]; 24 inline void getsa(char *s,int m){ 25 static int t1[N],t2[N],t3[N],*x=t1,*y=t2,*c=t3; 26 memset(c,0,sizeof(int)*(m+1)); 27 for(int i=1;i<=n;++i)++c[x[i]=s[i]-'a'+1]; 28 for(int i=1;i<=m;++i)c[i]+=c[i-1]; 29 for(int i=1;i<=n;++i)sa[c[x[i]]--]=i; 30 for(int len=1;len<=n;len<<=1){ 31 int num=0; 32 for(int i=n-len+1;i<=n;++i)y[++num]=i; 33 for(int i=1;i<=n;++i)if(sa[i]>len)y[++num]=sa[i]-len; 34 memset(c,0,sizeof(int)*(m+1)); 35 for(int i=1;i<=n;++i)++c[x[i]]; 36 for(int i=1;i<=m;++i)c[i]+=c[i-1]; 37 for(int i=n;i;--i)sa[c[x[y[i]]]--]=y[i]; 38 swap(x,y);memset(x,0,sizeof(int)*(n+1)); 39 x[sa[1]]=m=1; 40 for(int i=2;i<=n;++i) 41 x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+len]==y[sa[i-1]+len])?m:++m; 42 if(m==n)break; 43 } 44 for(int i=1;i<=n;++i)rk[sa[i]]=i; 45 for(int i=1,k=0;i<=n;h[rk[i++]]=k,k=k?k-1:0) 46 while(s[i+k]==s[sa[rk[i]-1]+k])++k; 47 } 48 int st1[20][N],st2[20][N],lg2[N],bin[30]; 49 int dq[N],ba,l[N],r[N]; 50 inline void init(){ 51 for(int i=0;i<=25;++i)bin[i]=1<<i; 52 for(int i=2;i<=n;++i)lg2[i]=lg2[i>>1]+1; 53 for(int i=1;i<=n;++i)st1[0][i]=st2[0][i]=a[sa[i]]; 54 for(int j=1;j<=lg2[n];++j) 55 for(int i=1;i<=n;++i) 56 st1[j][i]=min(st1[j-1][i],st1[j-1][i+bin[j-1]]), 57 st2[j][i]=max(st2[j-1][i],st2[j-1][i+bin[j-1]]); 58 h[1]=-100;h[n+1]=-50;ba=1;dq[1]=1; 59 for(int i=2;i<=n+1;++i){ 60 l[i]=r[i]=i; 61 while(h[i]<=h[dq[ba]])r[dq[ba]]=i-1,--ba; 62 l[i]=dq[ba]+1;dq[++ba]=i; 63 } 64 } 65 inline int ask1(int l,int r){ 66 return min(st1[lg2[r-l+1]][l],st1[lg2[r-l+1]][r-bin[lg2[r-l+1]]+1]); 67 } 68 inline int ask2(int l,int r){ 69 return max(st2[lg2[r-l+1]][l],st2[lg2[r-l+1]][r-bin[lg2[r-l+1]]+1]); 70 } 71 LL an1[N],an2[N]; 72 int main(){ 73 scanf("%d%s",&n,s+1); 74 for(int i=1;i<=n;++i)a[i]=read(); 75 getsa(s,27); 76 //for(int i=1;i<=n;++i)printf("sa[%d]=%d %d ",i,sa[i],h[i]); 77 init(); 78 memset(an2,-0x3f,sizeof(LL)*(n+2)); 79 for(int i=2;i<=n;++i){ 80 // cout<<l[i]<<" "<<r[i]<<endl; 81 an1[h[i]]+=1ll*(i-l[i]+1)*(r[i]-i+1); 82 LL t=1ll*ask2(l[i]-1,i-1)*ask2(i,r[i]); 83 an2[h[i]]=max(t,an2[h[i]]); 84 t=1ll*ask1(l[i]-1,i-1)*ask1(i,r[i]); 85 an2[h[i]]=max(t,an2[h[i]]); 86 } 87 for(int i=n-2;~i;--i){ 88 an1[i]+=an1[i+1]; 89 if(an1[i+1])an2[i]=max(an2[i+1],an2[i]); 90 } 91 for(int i=0;i<n;++i)printf("%lld %lld ",an1[i],an2[i]==an2[n+1]?0:an2[i]); 92 return 0; 93 }
字符串
HEOI的题，sa+主席树+二分答案
求区间内子串和一个固定串的lcp
照例先跑sa，处理出h。照例有st表处理h。（哪来的例？
然后我们的操作的下标基于h的下标，特殊的有标注
考虑主席树（基于原串），主席树的用途为查询前趋和后继。
具体操作为先查询rank，然后查询rank的串和rank+1的串。
然后发现因为有区间的限制每个子串能够作出贡献的最大长度不同。
考虑二分答案，二分出最后的长度，
用主席树查询（固定串后缀排名的）前趋和后继，
再用st表check最大长度是否符合即可
次题数据弱，暴力从固定串排名向左右分别扩展可过。（跑得比正解快。。。
1 #include<bits/stdc++.h> 2 #define N 200050 3 using namespace std; 4 int n,m; 5 char s[N]; 6 struct SA{ 7 int sa[N],h[N],rk[N]; 8 int rt[N],lc[N*20],rc[N*20],sum[N*20],tot; 9 int st[N][18],lg2[N],bin[30]; 10 inline void getsa(char *s,int m){ 11 int t1[N],t2[N],t3[N],*x=t1,*y=t2,*c=t3; 12 memset(c,0,sizeof(int)*(m+1)); 13 for(int i=1;i<=n;++i)++c[x[i]=s[i]-'a'+1]; 14 for(int i=1;i<=m;++i)c[i]+=c[i-1]; 15 for(int i=1;i<=n;++i)sa[c[x[i]]--]=i; 16 for(int len=1;len<=n;len<<=1){ 17 int num=0; 18 for(int i=n-len+1;i<=n;++i)y[++num]=i; 19 for(int i=1;i<=n;++i)if(sa[i]>len)y[++num]=sa[i]-len; 20 memset(c,0,sizeof(int)*m); 21 for(int i=1;i<=n;++i)++c[x[i]]; 22 for(int i=1;i<=m;++i)c[i]+=c[i-1]; 23 for(int i=n;i;--i)sa[c[x[y[i]]]--]=y[i]; 24 swap(x,y);memset(x,0,sizeof(int)*(n+1)); 25 x[sa[1]]=m=1; 26 for(int i=2;i<=n;++i) 27 x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+len]==y[sa[i-1]+len])?m:++m; 28 if(m==n)break; 29 } 30 for(int i=1;i<=n;++i)rk[sa[i]]=i; 31 } 32 inline void geth(char *s){ 33 for(int i=1,k=0;i<=n;h[rk[i++]]=k,k=(!k)?0:k-1) 34 while(s[i+k]==s[sa[rk[i]-1]+k])++k; 35 } 36 inline void add(int &g,int f,int l,int r,int x){ 37 if(!g)g=++tot;sum[g]=sum[f]+1; 38 if(l==r)return; 39 const int m=l+r>>1; 40 if(x<=m)rc[g]=rc[f],add(lc[g],lc[f],l,m,x); 41 else lc[g]=lc[f],add(rc[g],rc[f],m+1,r,x); 42 } 43 inline int getrank(int g,int f,int l,int r,int x){ 44 if(l==r)return sum[g]-sum[f]; 45 if(!(sum[g]-sum[f]))return 0; 46 const int m=l+r>>1; 47 if(x<=m)return getrank(lc[g],lc[f],l,m,x); 48 return sum[lc[g]]-sum[lc[f]]+getrank(rc[g],rc[f],m+1,r,x); 49 } 50 inline int getnum(int g,int f,int l,int r,int x){ 51 if(l==r)return l; 52 const int m=l+r>>1; 53 if(x<=sum[lc[g]]-sum[lc[f]]) 54 return getnum(lc[g],lc[f],l,m,x); 55 return getnum(rc[g],rc[f],m+1,r,x-(sum[lc[g]]-sum[lc[f]])); 56 } 57 inline void init(){ 58 for(int i=0;i<=20;++i)bin[i]=1<<i; 59 for(int i=1;i<=n;++i) 60 add(rt[i],rt[i-1],1,n,rk[i]); 61 for(int i=2;i<=n;++i)lg2[i]=lg2[i>>1]+1; 62 for(int i=1;i<=n;++i)st[i][0]=h[i]; 63 for(int j=1;j<=lg2[n];++j) 64 for(int i=1;i<=n;++i) 65 st[i][j]=min(st[i][j-1],st[i+bin[j-1]][j-1]); 66 } 67 inline int askmin(int x,int y){ 68 x=rk[x];y=rk[y]; 69 if(x==y)return n-sa[x]+1; 70 if(x>y)swap(x,y); 71 return min(st[x+1][lg2[y-x]],st[y-bin[lg2[y-x]]+1][lg2[y-x]]); 72 } 73 inline bool check(int l,int r,int c,int len){ 74 int t=getrank(rt[r],rt[l-1],1,n,rk[c]); 75 if(t){ 76 int k=getnum(rt[r],rt[l-1],1,n,t),p=askmin(sa[k],c); 77 if(p>=len)return true; 78 } 79 if(t!=r-l+1){ 80 int k=getnum(rt[r],rt[l-1],1,n,t+1),p=askmin(sa[k],c); 81 if(p>=len)return true; 82 } 83 return false; 84 } 85 }K; 86 int main(){ 87 scanf("%d%d%s",&n,&m,s+1); 88 K.getsa(s,27);K.geth(s);K.init(); 89 for(int i=1,l,r,mid,a,b,c,d;i<=m;++i){ 90 scanf("%d%d%d%d",&a,&b,&c,&d); 91 l=0,r=min(b-a+1,d-c+1)+1; 92 while(l+1<r){ 93 mid=l+r>>1; 94 if(K.check(a,b-mid+1,c,mid))l=mid; 95 else r=mid; 96 } 97 printf("%d ",l); 98 } 99 return 0; 100 }
喵星球上的点名
个人感觉是几道题里面最难的。。。（思维僵化的文化课选手
先把所有串接起来跑sa，处理出h数组，
然后直接对每个询问在h数组上暴力向两边扩展统计答案即可AC
但我们还是要找一个合法的复杂度。
利用st表+二分可以在log的时间复杂度内找到对应的区间。
用主席树维护一下即可（好像叫数颜色？？？）然后第一问就ok了
对于第二问，可以用莫队，把上一问处理出的区间离线，
在每只喵第一次加入时加入m-i，这只喵完全滚粗时再减去m-i。
还可以用树状数组，详见：%%%
View Codeupd:后缀数组专题二
外星联络
裸的后缀数组，考察对h的应用，如果对h数组真正理解就是秒切
SvT
(我并不知道题目名字是什么鬼)
还是稍简单的一道题。
考虑将单次询问按rank排序，存入数组，之后分治解决。
这里粘一下函数，a数组中存的是排名，ask返回h数组区间最小值的位置。
1 int solve(int l,int r){ 2 if(l==r)return 0; 3 int t=ask(a[l]+1,a[r]); 4 int k=lower_bound(a+l,a+r+1,t)-a; 5 int ret=h[t]*(r-k+1)*(k-l); 6 ret+=solve(l,k-1); 7 ret+=solve(k,r); 8 return ret; 9 }
其实看代码已经很显然了。
好多人看到这种打法都会疑问复杂度为nlog2n（你一眼看穿我也没话说
然后这里证明一下复杂度为nlogn
考虑lower_bound调用的次数，每次调用都会产生一个左区间的右端点，
所以lower_bound至多调用n次，复杂度为nlogn
股市的预测
新思想：关键点
考虑枚举相同串的长度，设为len，
每隔len设立一个关键点。
在关键点处统计包含这个关键点的长度为len的串对答案的贡献
具体做法：对关键点i，找出对应的j=i+len+m，求出向左和向右最长的匹配区间的长度，记为l和r，对len取min。
统计答案用max(0,l+r-len);
跳蚤
（然而并不是uoj的题）
想题的心路历程：
一开始发现字典序最大的后缀对答案的影响很大。然后自以为答案处在最后一个串上。然后伪了。
扩展一下，当最后的串被砍断后，答案出在倒数第二个串上，然后想二分（答案出现串的排名）
然后好像没伪。但二分完了之后，知道了答案串位置的排名，却不知道具体长度。
然后考虑二分（答案的长度），在对应长度处固定砍一刀。然后经rnb点拨，这玩意不具有单调性。
又经rnb点拨，其实应该二分（答案的长度的上界），区别就是必须在这个二分出的长度以内砍一刀，
而不是在长度处砍一刀。然后这个东西是具有单调性的。
1 #include<bits/stdc++.h> 2 #define N 100050 3 using namespace std; 4 int n,k,tot; 5 char s[N]; 6 int sa[N],rk[N],h[N]; 7 inline void getsa(char *s,int m){ 8 static int t[3][N],*x=t[0],*y=t[1],*c=t[2]; 9 memset(c,0,sizeof(int)*(m+1)); 10 for(int i=1;i<=n;++i)++c[x[i]=s[i]-'a'+1]; 11 for(int i=1;i<=m;++i)c[i]+=c[i-1]; 12 for(int i=1;i<=n;++i)sa[c[x[i]]--]=i; 13 for(int len=1;len<=n;len<<=1){ 14 int num=0; 15 for(int i=n-len+1;i<=n;++i)y[++num]=i; 16 for(int i=1;i<=n;++i)if(sa[i]>len)y[++num]=sa[i]-len; 17 memset(c,0,sizeof(int)*(m+1)); 18 for(int i=1;i<=n;++i)++c[x[i]]; 19 for(int i=1;i<=m;++i)c[i]+=c[i-1]; 20 for(int i=n;i;--i)sa[c[x[y[i]]]--]=y[i]; 21 swap(x,y);memset(x,0,sizeof(int)*(n+1)); 22 x[sa[1]]=m=1; 23 for(int i=2;i<=n;++i) 24 x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+len]==y[sa[i-1]+len])?m:++m; 25 if(m==n)break; 26 } 27 for(int i=1;i<=n;++i)rk[sa[i]]=i; 28 for(int i=1,k=0;i<=n;h[rk[i++]]=k,k=k?k-1:0) 29 while(s[i+k]==s[sa[rk[i]-1]+k])++k; 30 } 31 struct node{ 32 int l,r; 33 friend bool operator < (const node &a,const node &b){ 34 return a.l<b.l; 35 } 36 }q[N]; 37 inline bool check(){ 38 sort(q+1,q+tot+1); 39 static int ma[N];memset(ma,0,sizeof(ma)); 40 for(int i=1;i<=tot;++i)ma[q[i].r]=max(ma[q[i].r],i); 41 int ju=0; 42 for(int i=1,las=0,ts=1;i<=n;++i){ 43 while(ts<=tot&&q[ts].l==i)++ts; 44 if(ma[i]>las)las=ts-1,++ju; 45 } 46 return ju<=k; 47 } 48 int main(){ 49 scanf("%d%s",&k,s+1);n=strlen(s+1);--k; 50 getsa(s,27); 51 int l,r,pos,mid; 52 for(l=n-1;;--l)if(s[sa[l]]!=s[sa[l+1]])break; 53 r=n; 54 while(l+1<r){ 55 mid=l+r>>1; 56 tot=0; 57 for(int i=mid+1,mi=n+1;i<=n;++i){ 58 mi=min(mi,h[i]); 59 q[++tot]=(node){sa[i],sa[i]+mi-1}; 60 } 61 if(check())r=mid; 62 else l=mid; 63 } 64 pos=r; 65 r=n-sa[pos]+1;l=0; 66 while(l+1<r){ 67 mid=l+r>>1; 68 tot=0;q[++tot]=(node){sa[pos],sa[pos]+mid-1}; 69 for(int i=pos+1,mi=mid;i<=n;++i){ 70 mi=min(mi,h[i]); 71 q[++tot]=(node){sa[i],sa[i]+mi-1}; 72 } 73 if(check())r=mid; 74 else l=mid; 75 } 76 for(int i=sa[pos];i<=sa[pos]+r-1;++i)putchar(s[i]); 77 puts(""); 78 return 0; 79 }