大意: 给定串s, q个询问(l,r,k), 求子串s[l,r]的第kk次出现位置.
这是一篇很好的题解：
https://blog.csdn.net/sdauguanweihong/article/details/100063096
加点个人：
我对上面的题解更为详细的解释下：
后缀数组处理出来的heigth[] 数组 有个这样的性质：
对于排名 a 的后缀字符串 与排名 b 的后缀字符串 ，他们的最长公共前缀的长度为 min{heigth[a+1],heigth[a+2],heigth[b]};
依据这样的性质就可以二分线段树出[l,r] 这个字符串 是在多少排名的区间[L,R]了；
注意：我本想贪图方便用先二分l然后判断[l,pos] 的最小值复杂度为log*log 这个会T的
所以找这个区间要用log的方法，就是在存了最小值的线段树里面去搜左孩子啊右孩子什么的
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = ;
char s[maxn];
int y[maxn],x[maxn],c[maxn],sa[maxn],rk[maxn],height[maxn],wt[];
int n,k,q; int get_SA(int m){
for(int i= ; i<=m ; i++) c[i]=;
for(int i= ; i<=n ; i++) sa[i]=;
for(int i= ; i<=n ; i++) ++c[x[i]=s[i]];
for(int i= ; i<=m ; i++) c[i]+=c[i-];
for(int i=n ; i>= ; i--) sa[c[x[i]]--]=i;
for(int k= ; k<=n ; k<<=){
int num=;
for(int i=n-k+ ; i<=n ; i++) y[++num]=i;
for(int i= ; i<=n ; i++) if(sa[i]>k) y[++num]=sa[i]-k;
for(int i= ; i<=m ; i++) c[i]=;
for(int i= ; i<=n ; i++) ++c[x[i]];
for(int i= ; i<=m ; i++) c[i]+=c[i-];
for(int i=n ; i>= ; i--) sa[c[x[y[i]]]--]=y[i],y[i]=;
swap(x,y);
x[sa[]]=;
num=;
for(int i= ; i<=n ; i++)
x[sa[i]]=(y[sa[i]]==y[sa[i-]] && y[sa[i]+k]==y[sa[i-]+k]) ? num : ++num;
if (num==n) break;
m=num;
}
}
int get_height() {
int k=;
for (int i=; i<=n; ++i) rk[sa[i]]=i;
for (int i=; i<=n; ++i) {
if (rk[i]==) continue;
if (k) --k;
int j=sa[rk[i]-];
while (j+k<=n && i+k<=n && s[i+k]==s[j+k]) ++k;
height[rk[i]]=k;
}
} int mi[maxn<<];
void pushup(int rt){
mi[rt]=min(mi[rt<<],mi[rt<<|]);
}
void build(int l,int r,int rt)
{
if ( l==r )
{
mi[rt]=height[l];
return ;
}
int m = (l+r) >> ;
build(l,m,rt<<);
build(m+,r,rt<<|);
pushup(rt);
} int solvel(int o , int l , int r , int x , int v){
int mid=(l+r)>>;
if(r<=x){
if(l==r) return mi[o]>=v?l:-;
if(mi[o<<|]<v) return solvel(o<<|,mid+,r,x,v);
int t=solvel(o<<,l,mid,x,v);
return t==-?mid+:t;
}
if(mid>=x) return solvel(o<<,l,mid,x,v);
int R=solvel(o<<|,mid+,r,x,v);
if (R==-||R>mid+) return R;
int L = solvel(o<<,l,mid,x,v);
return L==-?R:L;
} int solver(int o, int l, int r, int x, int v){
int mid=(l+r)>>;
if (x<=l) {
if (l==r) return mi[o]>=v?l:-;
if (mi[o<<]<v) return solver(o<<,l,mid,x,v);
int t = solver(o<<|,mid+,r,x,v);
return t==-?mid:t;
}
if (mid<x) return solver(o<<|,mid+,r,x,v);
int L = solver(o<<,l,mid,x,v);
if (L==-||L<mid) return L;
int R = solver(o<<|,mid+,r,x,v);
return R==-?L:R;
} int tot;
int lson[maxn<<],rson[maxn<<],T[maxn],cc[maxn<<];
void zhu_build(int &root,int l,int r)
{
root=++tot;
if ( l==r ) return;
int mid=(l+r)/;
zhu_build(lson[root],l,mid);
zhu_build(rson[root],mid+,r);
}
void update(int root,int &rt,int p,int val,int l,int r)
{
rt=++tot;
lson[rt]=lson[root],rson[rt]=rson[root];
cc[rt]=cc[root]+val;
if ( l==r ) return;
int mid=(l+r)/;
if ( p<=mid ) update(lson[rt],lson[rt],p,val,l,mid);
else update(rson[rt],rson[rt],p,val,mid+,r);
}
int query(int rt_,int rt,int l,int r,int k)
{
if ( l==r ) return l;
int mid=(l+r)/;
int sum=cc[lson[rt_]]-cc[lson[rt]];
if ( sum>=k ) return query(lson[rt_],lson[rt],l,mid,k);
else return query(rson[rt_],rson[rt],mid+,r,k-sum);
} int main(){
int _;scanf("%d",&_);
while(_--){
scanf("%d%d%s",&n,&q,s+); get_SA(); get_height();
build(,n,);
tot=;
zhu_build(T[],,n);
for(int i= ; i<=n ; i++){
update(T[i-],T[i],sa[i],,,n); }
while(q--){
int l,r;scanf("%d%d%d",&l,&r,&k);
int p=rk[l];
int ql = p>?solvel(,,n,p,r-l+)-:;
int qr = p<n?solver(,,n,p+,r-l+):n;
if (ql<) ql = p;
if (qr<) qr = p;
int ans;
if(qr-ql+<k)
ans=-;
else
ans=query(T[qr],T[ql-],,n,k); printf("%d\n",ans);
}
}
}