link：https://codeforces.com/problemset/problem/1968/G2
给一个字符串 \(s\)，定义 \(f_k\) 表示：将 \(s\) 划分成恰好 \(k\) 段 \(w_1,\dots,w_k\) 之后， \(LCP(w_1,\dots,w_k)\)$ 的最大值，其中LCP表示最长公共前缀。求 \(f_l,\dots,f_r\) （其实和求所有 \(f\) 没什么区别）
\(\sum |s|\leq 2\times 10^5\).
对于这样的划分问题，首先需要注意到的（显然的事实）是： \(s\) 的前缀一定会作为某个 \(w_i\) 出现，因此LCP也一定是 \(s\) 的前缀。
那么就可以想，暴力枚举 \(s\) 的前缀 \(s[1,\dots,k]\)，如果其至多能在 \(s\) 当中不相交地出现 \(c\) 次，那么 \(f_1,\dots,f_c\) 都至少是 \(k\).
判断 \(s\) 前缀在 \(s\) 中不相交地出现几次，直接用KMP是稳定 \(O(n)\) 的，对每个 \(k\) 处理就退化成 \(O(n^2)\) 了。
难道会是什么神奇的后缀结构吗（并不会后缀xxx系列…），可恶，难道就到此为止了吗…
不可以，div3不会是这样的难度，让我们来想点稍微简单的东西，KMP麻烦就麻烦在要把整个串跑一遍，而我们知道枚举前缀 \(k\) 的话，至多有 \(O(n/k)\) 段，这里其实差了很多，也许可以尝试从这里想。如果写哈希的话，要怎么从当前一段快速跳到下一段，每次查询的前缀都不一样，用哈希也只能把整个串扫一遍…
等一下！Z函数是求什么来着的？ \(z_i\) 能处理 \(s\) 和 \(s[i,\dots,n]\) 的LCP，如果用Z函数来跳，假设当前在位置 \(i\)，那只要在 \([i+1,n]\) 当中找到最小的 \(j\) 使得 \(z_j\geq k\) ，然后把 \(i\) 跳到 \(j\) 就可以了，寻找 \(j\) 的过程可以用静态RMQ+二分完成，这样复杂度就是 \(O(\log n\times (n/k))\) 了，对每个 \(k\) 跑一遍，算出出现次数 \(c\) ，然后给 \(f_1,\dots f_c\) 做一个取max的操作，前缀取max也可用类似前缀和那样通过打标记完成。
总复杂度 \(O(n\log^2 n)\).
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define endl '\n'
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int N=2e5+5;
vector<int> exKMP(const string &s){int n=s.length();vector<int> z(n);for(int i=1,l=0,r=0;i<n;++i){if(i<=r&&z[i-l]<r-i+1)z[i]=z[i-l];else{z[i]=max(0,r-i+1);while(i+z[i]<n&&s[z[i]]==s[i+z[i]])++z[i];}if(i+z[i]-1>r)l=i,r=i+z[i]-1;}return z;
}int n,l,r,tag[N];
int f[21][N],Log[N];
string s;
int query(int l,int r){int k=Log[r-l+1];return max(f[k][l],f[k][r-(1<<k)+1]);
}
int main(){fastio;Log[0]=-1;rep(i,1,N-5)Log[i]=Log[i>>1]+1;int tc;cin>>tc;while(tc--){cin>>n>>l>>r>>s;auto z=exKMP(s);rep(i,0,n-1)f[0][i]=z[i];rep(i,0,n)tag[i]=0;rep(j,1,20)for(int i=0;i+(1<<j)-1<n;i++)f[j][i]=max(f[j-1][i],f[j-1][i+(1<<(j-1))]);auto work=[&](int k){int cnt=1;for(int i=0;i<n;){int L=i+k,R=n-1,ret=-1;while(L<=R){int mid=(L+R)>>1;if(query(i+k,mid)>=k){ret=mid;R=mid-1;}else L=mid+1;}if(ret==-1)break;cnt++;i=ret;}tag[cnt]=max(tag[cnt],k);};rep(i,1,n)work(i);tag[n+1]=0;for(int i=n;i>=1;i--)tag[i]=max(tag[i],tag[i+1]);rep(i,l,r)cout<<tag[i]<<' ';cout<<endl;}return 0;
}
