【MX-X1-T4】KDOI-05
现在有一个字符串 \(S\)，\(q\) 次询问，每次给出 \((i,k)\)，求有多少个非空字符串 \(A\)，使得存在可空字符串 \(B_1,B_2,\dots,B_{k-1}\) 满足：
\[S[1,i]=AB_1AB_2A\cdots AB_{k-1}A \]\(1\le n,q,\le 2\times 10^5\)
转化题意，当 \(k>1\) 时，相当于 \(A\) 要满足两个条件：
- \(A\) 是 \(S[1,i]\) 的一个 border；
- \(A\) 在 \(S\) 的前 \(i\) 个字符中不重叠地出现了 \(\ge k\) 次。
我们考虑建出 \(S\) 的 Fail 树，然后会发现，根节点到 \(i\) 点链上的结点都是 \(i\) 的 border，且从上到下，它们在 \(S[1,i]\) 的出现次数应当是单调不增的。设根节点到 \(i\) 的链上有一点 \(u\)，满足其是最靠后的 \(S[1,i]\) 的出现次数 \(\ge k\) 次的，若能求出它，答案就是 \(dep_u\)。
如果求出来了相关东西，树上倍增就可以做了，我们就要检查 \(S[1,u]\) 的第 \(k\) 次不重叠出现位置是否 \(\le i\)。
怎么求这个呢？考虑从字符串的 \(u\) 位置开始跳，每次找到这个位置后面第一个后缀，使得其与整个 \(S\) 的 LCP \(\ge u\)，这里可以求一个 \(Z\) 函数。因为要求不重复，每步至少跳 \(u\) 步，如果我们每次能快速定位到下一位置的话，复杂度是一个调和级数。
定位的话有一个很巧妙的思路，我们考虑从小到大枚举这个 \(u\)，表示现在要求 \(S[1,u]\) 在 \(S\) 中的不重叠出现位置。然后我们用并查集，等到将 \(S[1,u]\) 求完后，我们把所有 \(Z_p=u\) 的位置给删去，然后留给下一次 \(S[1,u+1]\) 的并查集中，所有代表元就都是 \(\ge u+1\) 的了。
具体来说就是最开始的时候所有 \(fa_i=i\)，然后首先对 \(Z_p=0\) 的位置，令其 \(fa_p=p+1\)，表示依附于后一位，这样跳的时候可以直接跳过这个位置。而后面的也同理。
【扩展】类并查集链表 trick
一般用于维护一个序列内的标记信息：
- 将某个被标记的数字取消标记；
- 查找某数字右侧第一个被标记的数字；
- 遍历一个区间 \([l,r]\) 被标记的数字。
我们对于每个数维护一个指针表示自己以及右边第一个被标记的数字。若 \(i\) 被标记，令 \(f_i\leftarrow i\)，否则令 \(f_i\leftarrow i+1\)，这样通过并查集的 find 操作就可以找到右侧第一个被标记的数字了。
遍历区间时令 \(cur\leftarrow find(l)\)，下一步就令 \(cur\leftarrow find(cur+1)\)，直至 \(cur>r\)。
例如这道题，我们维护 \(Z_p\ge u\) 的数拥有标记，要支持删除标记和找到右边第一个有标记位置，用这个 trick 再好不过了。
参考：
-
类并查集链表
-
Solution from EuphoricStar
Code:
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define llINF 0x3f3f3f3f3f3f3f3f
#define ui unsigned int
using namespace std;
const int N=2e5+10;
int n,q,fail[N],z[N],f[N][25],dep[N],fa[N];
vector<int> layer[N],pos[N];
int get(int x){ return x==fa[x]?x:fa[x]=get(fa[x]); }
string s;
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>s;s=" "+s;for(int i=2;i<=n;i++){int j=fail[i-1];while(j&&s[j+1]!=s[i]) j=fail[j];if(s[j+1]==s[i]) j++;fail[i]=j;}for(int i=1;i<=n;i++){f[i][0]=fail[i];dep[i]=dep[fail[i]]+1;for(int j=1;j<=19;j++) f[i][j]=f[f[i][j-1]][j-1];}z[1]=n;for(int i=2,l=0,r=0;i<=n;i++){if(z[i-l+1]<r-i+1) z[i]=z[i-l+1];else{z[i]=max(0,r-i+1);while(i+z[i]<=n&&s[1+z[i]]==s[i+z[i]]) z[i]++;l=i,r=i+z[i]-1;}}for(int i=1;i<=n+1;i++) fa[i]=i;for(int i=1;i<=n;i++){if(!z[i]) fa[i]=i+1;else layer[z[i]].push_back(i);}for(int i=1;i<=n;i++){int cur=i;pos[i].push_back(cur);while(cur+i<=n){int tmp=get(cur+1);if(tmp==n+1) break;cur=tmp+i-1;pos[i].push_back(cur);}for(auto u:layer[i]) fa[u]=u+1;}cin>>q;while(q--){int x,y; cin>>x>>y;if(y==1){cout<<"1\n";continue;}int cur=x;for(int i=19;i>=0;i--) if(f[cur][i]&&(pos[f[cur][i]].size()<y||pos[f[cur][i]][y-1]>x)) cur=f[cur][i];cur=f[cur][0];cout<<dep[cur]<<"\n";}return 0;
}