【Atcoder】 [ABC240Ex] Sequence of Substrings

题目链接

Atcoder方向
Luogu方向

题目解法

先考虑一个性质，选出的子串长度不会超过 $\sqrt{2n}$
考虑最劣的选法是选出长度为 $1,2,3,...$ 的子串（如果后一个选出的串比前一个子串长度大超过1，那么后一个选出的子串一定可以将自己长度变为前一个子串的长度$+1$），所以 $\frac{m(m+1)}{2}\ge n$ 的最大的 $m\le \sqrt{2n}$
考虑用类似 $trie$ 树的方式把长度 $\le \sqrt{2n}$ 的子串排序，注意对于字典序相同的子串，需要按照起点从大到小排序
然后从小到大在树状数组上修改及查询即可，这都是常规操作
时间复杂度 $O(n\sqrt{n}logn)$

#include <bits/stdc++.h>
#define lowbit(x) x&-x 
using namespace std;
typedef pair<int,int> pii;
const int N(25200);
int n,m,MX=230,rk[N],idx,tr[N];
char str[N];
pii b[N*250];
inline int read(){int FF=0,RR=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;return FF*RR;
}
void solve(vector<int> vec,int len){if(!vec.size()||len>MX) return;vector<int> v0,v1;v0.clear(),v1.clear();for(int i=0;i<vec.size();i++){if(vec[i]+len>n) continue;if(str[vec[i]+len]==48) v0.push_back(vec[i]);else v1.push_back(vec[i]);}for(int i=v0.size()-1;~i;i--) b[++m]=make_pair(v0[i],len);solve(v0,len+1);for(int i=v1.size()-1;~i;i--) b[++m]=make_pair(v1[i],len);solve(v1,len+1);
}
int ask(int x){if(!x) return 0;int res=0;for(;x;x-=lowbit(x)) res=max(res,tr[x]);return res;
}
void upd(int x,int val){for(;x<=n;x+=lowbit(x)) tr[x]=max(tr[x],val);
}
int main(){n=read();scanf("%s",str+1);vector<int> vec;for(int i=1;i<=n;i++) vec.push_back(i);solve(vec,0);
//	for(int i=1;i<=m;i++) cout<<b[i].first<<' '<<b[i].second<<'\n';for(int i=1;i<=m;i++){int t=ask(b[i].first-1);upd(b[i].first+b[i].second,t+1);}printf("%d",ask(n));return 0;
}