ABC240Ex Sequence of Substrings
LIS 的好题改编。
约定
\(S(l,r)\) 为字符串 \(s\) 中第 \(l\) 位到底 \(r\) 位。
\(S(l,r)<S(x,y)\) 为字符串中 \([l,r]\) 的子串字典序比 \([x,y]\) 的子串小。
前置
LIS 的 \(n\log n\) 求法。
题解
我们考虑按照类似于朴素 LIS 的方式设状态，\(f[l][r]\) 表示 \([l,r]\) 这个区间作为当前选的最后一个划分，所得到的 LIS 最大值。
显然有转移：
\[f[l][r]=\max(f[x][y])+1 \]要求 \(S(x,y)<S(l,r)\)。
我们可以使用一个很经典的判断两个字符串字典序大小的技巧，先使用 hash+二分 求出 LCP（最长公共前缀），然后用比较 LCP 的下一位求字典序大小。
对于方程里的 \(\max\) 操作，类似于 LIS 的 \(n\log n\) 做法维护一个 \(g\) 数组，之前 \(g[i]\) 表示 LIS 为 \(i\) 的最小数字，同时 \(g\) 数组有单调递增的性质。现在还是维护这样的一个 \(g\) 数组，\(g[i]\) 表示 LIS 为 \(i\) 的字典序最小区间，\(g[i]\) 可以用一个 pair 类型维护。
当然为了方便，笔者把数组变成了 set，维护相同的东西，方便直接使用 lower_bound 查询。
每一个 \(f[l][r]\) 都要做一次上述转移，转移复杂度包含：\(g\) 数组查找的 \(O(\log n)\)，每次的查找的比较 \(O(\log n)\)，共 \(O(\log^2 n)\)。总共复杂度 \(O(n^2\log^2 n)\)。
这个复杂度是肯定过不了的，我们考虑从这题的性质上去优化。
每一个 \(S(l,r)\) 肯定是从一个比他小的串 \(S(x,y)\) 转移过来的，我们可以分两种情况讨论：
- \(S(l,r)\) 靠长度比 \(S(x,y)\) 大。
- \(S(l,r)\) 通过字符比较比 \(S(x,y)\) 大。
考虑通过 2 类型的方式转移，那么 \(S(l,r)\) 的长度肯定小于等于 \(S(x,y)\)。
考虑通过 1 类型做贡献的子串的最大长度是 \(B\)。显然 \(B\) 肯定是从 \(1\) 开始累加起来的，那么前面肯定出现过长度为 \(B-1,B-2,B-3,\cdots,1\) 通过 1 类型转移的子串，他们总共的长度为 \(\frac{(1+B)\times B}{2}\)，满足
\[\frac{(1+B)\times B}{2} \leq n \]解得
\[B \leq \sqrt{2n} \]说明了什么呢？
通过 1 类型做贡献的子串最大长度是 \(\sqrt{2n}\)，通过 2 类型做贡献的子串长度小于等于最大子串长度。
那么我们每次只需要求子串长度在 \(\sqrt{2n}\) 以内状态，即只需要求满足 \(r-l+1\leq \sqrt{2n}\) 所有 \(f[l][r]\)。
时间复杂度降至 \(O(n\sqrt n \log^2 n)\)。
擦一把汗还是可以过的，信友队高级组 T1 和这题重了,实测也可以跑过。
#include<bits/stdc++.h>
using namespace std;
#define mod 998244353
const int maxn=2e4+5e3+5;
#define ll long long
#define pii pair<int,int>
#define S second
#define F first
int n,B;
char s[maxn];
int ans;
ll sum[maxn],base[maxn];
unordered_map<int,int>f[maxn];
inline ll gt(int r,int l)
{
return (sum[r]-sum[l-1]*base[r-l+1]%mod+mod)%mod;
}
inline bool cmps(int x,int rx,int y,int ry)
{
return gt(rx,x)==gt(ry,y);
}
inline bool cmp(int x,int rx,int y,int ry)
{
int l=1,r=min(rx-x+1,ry-y+1),ans=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(cmps(x,x+mid-1,y,y+mid-1)) l=mid+1,ans=mid;
else r=mid-1;
}
if(ans==min(rx-x+1,ry-y+1)) return rx-x+1<ry-y+1;
return s[x+ans]<s[y+ans];
}
struct node
{
int l,r,w;
bool operator<(const node a)const{return cmp(l,r,a.l,a.r);}
};
set<node>st;
pii fd[maxn];
int main()
{
scanf("%d",&n);
B=sqrt(2*n);
base[0]=1;for(int i=1;i<=n;i++) base[i]=base[i-1]*113%mod;
scanf("%s",s+1);
for(int i=1;i<=n;i++) sum[i]=(sum[i-1]*113+s[i]-'0'+mod)%mod;
for(int L=1;L<=n;L++)
{
for(int R=L;R<=n&&R<=L+B;R++)
{
auto it=st.lower_bound({L,R,0});
if(it!=st.begin()) f[L][R]=(--it)->w+1;
else f[L][R]=1;
}
for(int j=L;j;j--)
{
if(L-j+1>B) break;
if(fd[f[j][L]].F==0)
{
st.insert({j,L,f[j][L]});
fd[f[j][L]]={j,L};
}
else if(cmp(j,L,fd[f[j][L]].F,fd[f[j][L]].S))
{
st.erase({fd[f[j][L]].F,fd[f[j][L]].S,f[j][L]});
st.insert({j,L,f[j][L]});fd[f[j][L]]={j,L};
}
}
}
printf("%d",st.size());
}