题意
求区间l,r的子串在原串中第k次出现的位置。
链接：https://vjudge.net/contest/322094#problem/C
思路
比赛的时候用后缀自动机写的，TLE到比赛结束。
学了后缀数组后，发现这题用后缀数组写还简单些。
我们把样例aaabaabaaaab后缀排序后列出来：
比如我们的l,r,k为2,3,2，那么先找到2,3表示的子串为aa，后缀数组的height数组表示的是相邻两个后缀（排序后）的最长公共前缀长度，往这个方向去想，[l,r]这个子串肯定是某个后缀的前缀。我们先找到rk[l]（以l开始的后缀），这里rk[2]是6，容易发现6的前后可能会有公共前缀，如果这个公共前缀>=(r-l+1)，则这些前缀都有满足我们要找的子串。而且可以发现排序后的后缀的公共前缀长度是有单调性的，这里越接近6的公共前缀越长，越远离6的公共前缀越短，我们二分找出上下界即可，可以通过ST表查询出height[rk[x+1]~rk[y]]的最小值来找出x后缀和y后缀的最长公共前缀长度。
找出上下届后，这些后缀都是满足条件的，那么我们提前把所有sa[i]（排序后第i个后缀在原串中的位置）插入主席树，再在上下界中找第k小即可。
代码
#include<bits/stdc++.h>
const int N = 2e5 + 10;
using namespace std;
char s[N];
int len, M, rk[N], sa[N], tax[N], tp[N];
/*
sa[i]：排名为i的后缀的位置
rk[i]：从第i个位置开始的后缀的排名，把从第i个位置开始的后缀简称为后缀i
tp[i]：基数排序的第二关键字，意义与sa一样，即第二关键字排名为i的后缀的位置
tax[i]：i号元素出现了多少次。辅助基数排序
s：字符串，s[i]表示字符串中第i个字符串
*/
void jsort() //基数排序
{
for (int i = 0; i <= M; i++) tax[i] = 0;
for (int i = 1; i <= len; i++) tax[rk[i]]++;
for (int i = 1; i <= M; i++) tax[i] += tax[i - 1];
for (int i = len; i >= 1; i--) sa[ tax[rk[tp[i]]]-- ] = tp[i];
}
void suffixSort() //后缀排序
{
M = 75; //字符集的大小
for (int i = 1; i <= len; i++) rk[i] = s[i] - 'a' + 1, tp[i] = i;
jsort();
// Debug();
for (int w = 1, p = 0; p < len; M = p, w <<= 1)
{
//w:当前倍增的长度，w = x表示已经求出了长度为x的后缀的排名，现在要更新长度为2x的后缀的排名
//p表示不同的后缀的个数，很显然原字符串的后缀都是不同的，因此p = N时可以退出循环
p = 0;//这里的p仅仅是一个计数器000
for (int i = 1; i <= w; i++) tp[++p] = len - w + i;
for (int i = 1; i <= len; i++) if (sa[i] > w) tp[++p] = sa[i] - w; //这两句是后缀数组的核心部分，我已经画图说明
jsort();//此时我们已经更新出了第二关键字，利用上一轮的rak更新本轮的sa
swap(tp, rk);//这里原本tp已经没有用了
rk[sa[1]] = p = 1;
for (int i = 2; i <= len; i++)
rk[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++p;
//这里当两个后缀上一轮排名相同时本轮也相同
//Debug();
}
// for (int i = 1; i <= len; i++)
// printf("%d ", sa[i]);
}
//i号后缀：从i开始的后缀
//lcp(x,y):字符串x与字符串y的最长公共前缀，在这里指x号后缀与与y号后缀的最长公共前缀
int height[N];//lcp(sa[i],sa[i-1])，即排名为i的后缀与排名为i-1的后缀的最长公共前缀
int h[N];//height[rak[i]]，即i号后缀与它前一名的后缀的最长公共前缀
//性质：H[i]>=H[i-1]-1
void getHeight()
{
int j, k = 0;
for(int i = 1; i <= len; i++)
{
if(k) k--;
int j = sa[rk[i] - 1];
while(s[i + k] == s[j + k]) k++;
h[i]=height[rk[i]] = k;
//printf("%d\n", k);
}
}
/*
两个后缀的最大公共前缀lcp(x,y)=min(height[rank[x+1]~rank[y]])， 用rmq维护，O(1)查询
可重叠最长重复子串:height数组里的最大值
本质不同的子串的数量:枚举每一个后缀，第i个后缀对答案的贡献为len-sa[i]+1-height[i]
*/
/**********************主席树*********************/
int n, q, sz, num = 0;
int T[N];
int sum[N<<5], L[N<<5], R[N<<5];
#define mid (l+r)/2
inline int build(int l, int r)
{
int rt = ++ num;
sum[rt] = 0;
if (l < r)
{
L[rt] = build(l, mid);
R[rt] = build(mid+1, r);
}
return rt;
}
inline int update(int pre, int l, int r, int x)
{
int rt = ++ num;
L[rt] = L[pre];
R[rt] = R[pre];
sum[rt] = sum[pre]+1;
if (l < r)
{
if (x <= mid) L[rt] = update(L[pre], l, mid, x);
else R[rt] = update(R[pre], mid+1, r, x);
}
return rt;
}
inline int query(int u, int v, int l, int r, int k)
{
if (l >= r) return l;
int x = sum[L[v]] - sum[L[u]];
if (x >= k) return query(L[u], L[v], l, mid, k);
else return query(R[u], R[v], mid+1, r, k-x);
}
/*********************ST表**************/
int mm[N],dpMin[N][20];
//初始化Rmq,b数组下标从1开始，从0开始简单修改
void initRmq(int n,int b[]) //O(nlogn)预处理
{
mm[0]=-1;
for(int i=1;i<=n;i++)
{
mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
dpMin[i][0]=b[i];
}
for(int j=1;j<=mm[n];j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
{
dpMin[i][j]=min(dpMin[i][j-1],dpMin[i+(1<<(j-1))][j-1]);
}
}
}
int rmqMin(int x,int y)
{
int k=mm[y-x+1];
return min(dpMin[x][k],dpMin[y-(1<<k)+1][k]);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(sum,0,sizeof(sum));
memset(height,0,sizeof(height));
memset(dpMin,0,sizeof(dpMin));
memset(mm,0,sizeof(mm));
num=0;
int n,m;
scanf("%d%d",&n,&m);
scanf("%s",s+1);
len = strlen(s + 1);
suffixSort();
T[0]=build(1,n);
for(int i=1;i<=len;i++)
{
T[i]=update(T[i-1],1,n,sa[i]);
}
getHeight();
initRmq(n,height);
while(m--)
{
int x,y,k;
scanf("%d%d%d",&x,&y,&k);
int L=rk[x],R=rk[x];
int l=1,r=rk[x],g=y-x+1;
while(l<=r)
{
int h=(l+r)>>1;
if(h+1<=rk[x]&&rmqMin(h+1,rk[x])>=g)
{
r=h-1;
L=h;
// cout<<L<<" GG"<<endl;
}
else
l=h+1;
}
// cout<<L<<endl;
l=rk[x]+1,r=n;
while(l<=r)
{
int h=(l+r)>>1;
if(h>=rk[x]+1&&rmqMin(rk[x]+1,h)>=g)
{
l=h+1;
R=h;
}
else
r=h-1;
}
// printf("%d %d %d\n",rk[x],L,R);
if(R-L+1<k)
{
printf("-1\n");
}
else
{
printf("%d\n",query(T[L-1],T[R],1,n,k));
}
}
}
return 0;
}
/*
10
14 5
abcabcdabcddee
1 2 3
2 2 4
1 3 1
7 7 2
1 6 2
13 10
aabccaadeaaaa
*/