题目描述
给定一个长为 \(N\) 的字符串 \(S\),其中 \(1\le N\le 3000\)。对某个数对 \((K,L)\),其中 \(1\le L\le K\le N\),从 \(S\) 中取出所有 \(K\) 长度的子串,取出其所有长度为 \(L\) 的子串,将字典序最小的子串(如果存在并列则选择其中最左边的子串)在 \(S\) 中的起始位置 \(p_i\) 写入一个集合 \(P\)。
对于 \(1 \ldots N\) 中的每一个 \(v\),求出满足 \(|P|=v\) 的 \((K,L)\) 对的数量,时限为 \(2s\)。
题目分析
数据规模提示我们用 \(n^2\) 级别的算法解决问题。如果暴力枚举 \((K,L)\),那么求解 \(|P|\) 的过程将至多只有 \(O(\log n)\) 的余地,这似乎是很困难的(需要及其强大的预处理)
因此,我们想到考虑枚举 \((K,L)\) 中的一个要素!如果枚举 \(K\),那么我要考虑的事情就是:所有 \(K\) 长度的子串要如何用 \(O(n)\) 或 \(O(n \log n)\) 的复杂度统计出 \((K,1)\) 到 \((K,K)\) 的 \(|P|\)。既然不能枚举 \(L\),故只能考虑某个字串对哪些 \((K,L)\) 的 \(|P|\) 有贡献,然而,似乎所有的字串都有可能贡献!这必然转化为枚举所有字串,总复杂度将达到 \(O(n^3)\)!
故而只能去枚举 \(L\),沿用同样的思路,枚举 \(L\) 的好处显而易见:可能贡献的字串长度必须为 \(L\)!我们考虑一个字串 \(S_{i,i+L-1}\)(表示从 \(i\) 位置开头长度为 \(L\) 的字串),其为某个 \(S_{l,r}\) 的所有长度为 \(L\) 的子串中字典序最小的子串(如果存在并列则为其中最左边的子串),那可想而知,\(l\) 和 \(r\) 必然存在一个连续的范围,我们将这一连续的范围精确的表述出来:设
上面的字符串比大小遵循题述的比较方式,则有 \(l\) 和 \(r\) 的取值范围为:
从而对所有 \(K=r-l+1 \in [L,r_i-l_i+L-2]\),\(S_{i,i+L-1}\) 都可以贡献给 \((K,L)\) 的 \(|P|\)。如果我们已经算出了 \(l_i,r_i\),那么利用差分和前缀和,就很轻松的解决这类区间修改单点查询的统计问题快速查询,对每一个 \(L\) 时间复杂度为 \(O(n)\)。
最后的难点就在 \(l_i,r_i\) 的快速求解,注意到,\(l_i,r_i\) 中对 \(j\) 的选取遵循决策单调性(左/右侧第一个满足某种偏序关系的决策为其特征结构),因此我们考虑单调栈进行维护,此时对每一个 \(L\) 时间复杂度为 \(O(n)\),但是要求 \(O(1)\) 判断偏序关系,这是比较难的(\(\text{DP}\) 预处理可以做到)。当然,可以采用一种暴力的 \(O(\log n)\) 的查询方法。利用字符串哈希,二分找到第一个不一样的位置判断即可。
到此总的复杂度为 \(O(n^2 \log n)\),时限为 \(2s\),加上二分区间难以跑满 \(n\) 的规模,可以通过本题。
Code
点击查看代码
#include<bits/stdc++.h>
typedef unsigned long long ull;
using namespace std;
const int N=3e3+10;
const int base=131;
int n,l[N],r[N],d[N],sum,ans[N];
int st[N],top;
string s;
ull f[N],p[N];
void H(int n) {p[0]=1;for(int i=1;i<=n;i++) {f[i]=f[i-1]*base+(s[i]-'A'+1);p[i]=p[i-1]*base;}
}
ull GH(int l,int r) {return f[r]-f[l-1]*p[r-l+1];
}
bool cmp(int x,int y,int L) {//[x,x+L-1] is or isn't < [y,y+l-1]if(GH(x,x+L-1)==GH(y,y+L-1)) {if(x<y) return true;return false;}int l=1,r=L,pos;while(l<=r) {int mid=l+r>>1;if(GH(x,x+mid-1)==GH(y,y+mid-1)) l=mid+1;else {pos=mid;r=mid-1;}}if(s[x+pos-1]<s[y+pos-1]) return true;return false;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>s;s=" "+s;H(n);for(int L=1;L<=n;L++) {for(int i=1;i<=n;i++) {l[i]=d[i]=0;r[i]=n-L+2;}top=0;for(int i=1;i<=n-L+1;i++) {while(top&&cmp(i,st[top],L)) top--;if(top) l[i]=st[top];st[++top]=i;}top=0;for(int i=n-L+1;i>=1;i--) {while(top&&cmp(i,st[top],L)) top--;if(top) r[i]=st[top];st[++top]=i;}for(int i=1;i<=n-L+1;i++) {d[L]++;d[r[i]-l[i]+L-1]--;}sum=0;for(int K=L;K<=n;K++) {sum+=d[K];ans[sum]++;}}for(int v=1;v<=n;v++) cout<<ans[v]<<endl;return 0;
}