题意

给你一个长度为n的字符串，q次查询，每次查询给你三个数字, l, r, k
查询 查询从左往右 第k个 与子串 s[l…r] 相同的子串的左端点的位置
查询不到输出-1
1 ≤ n ≤ 1 e 5 , 1 ≤ q ≤ 1 e 5 1 \le n \le 1e5, 1 \le q \le 1e5 1≤n≤1e5,1≤q≤1e5

思路

对字符串后缀数组，根据sa数组建主席树，然后rmq预处理height数组
每一次查询，根据height数组二分找到一个最左的合法的左端点ansL，和最右的右端点ansR
然后在主席树上找区间[ansL, ansR]的第 k 大的位置就行。
如果ansR - ansL + 1 < k 则输出 -1

AC_code:

/* Algorithm: Author: anthony1314 Creat Time: Time Complexity: */


#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1e9 + 7
#define line printf("--------------");
const int maxn = 1e5+10;
int rt[maxn], ls[maxn*20], rs[maxn*20], sum[maxn*20], cnt;
/*主席树*/
void update(int &root, int pre, int l, int r, int k) {
	root = ++cnt;
	sum[root] = sum[pre] + 1;
	ls[root] = ls[pre];
	rs[root] = rs[pre];
	if (l == r) {
		return;
	}
	int mid = (l + r) / 2;
	if(k <= mid) {
		update(ls[root], ls[pre], l, mid, k);
	} else {
		update(rs[root], rs[pre], mid + 1, r, k);
	}
}
int query(int root, int pre, int l, int r, int k) {
	if (l == r) {
		return l;
	}
	int cmp = sum[ls[root]] - sum[ls[pre]];
	int mid = (l + r) / 2;
	if (cmp >= k) {
		return query(ls[root], ls[pre], l, mid, k);
	}
	return query(rs[root], rs[pre], mid + 1, r, k - cmp);
}
/*后缀数组*/
struct node {
	int sa[maxn],c[maxn],rank[maxn],height[maxn],t1[maxn], t2[maxn];
	void build_sa(int s[],int n,int m) {// 字符串 字符串长度+1 最大字符+1
		int i,j,p,*x=t1,*y=t2;
		for(i=0; i<m; i++)c[i]=0;
		for(i=0; i<n; i++)c[x[i]=s[i]]++;
		for(i=1; i<m; i++)c[i]+=c[i-1];
		for(i=n-1; i>=0; i--)sa[--c[x[i]]]=i;
		for(j=1; j<=n; j<<=1) {
			p=0;
			for(i=n-j; i<n; i++)y[p++]=i;
			for(i=0; i<n; i++)if(sa[i]>=j)y[p++]=sa[i]-j;
			for(i=0; i<m; i++)c[i]=0;
			for(i=0; i<n; i++)c[x[y[i]]]++;
			for(i=1; i<m; i++)c[i]+=c[i-1];
			for(i=n-1; i>=0; i--)sa[--c[x[y[i]]]]=y[i];
			swap(x,y);
			p=1;
			x[sa[0]]=0;
			for(i=1; i<n; i++)
				x[sa[i]]=y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+j]==y[sa[i]+j]?p-1:p++;
			if(p>=n)break;
			m=p;
		}
	}
	void getHeight(int s[],int n) {
		int i,j,k=0;
		for(i=0; i<n; i++)rank[sa[i]]=i;
		for(i=0; i<n; i++) {
			if(k)k--;
			j=sa[rank[i]-1];
			while(s[i+k]==s[j+k])k++;
			height[rank[i]]=k;
		}
	}
	/*初始化*/
	int mn[maxn][20];
	void init(int n) {
		cnt = 0;
		for (int i = 1; i < n; i++) {
			update(rt[i], rt[i - 1], 0, maxn, sa[i]);
		}
		for (int i = 1; i < n; i++) {
			mn[i][0] = height[i];
		}
		for (int i = 1; i < 20; i++) {
			for (int j = 1; j - 1 + (1 << i) < n; j++) {
				mn[j][i] = min(mn[j][i - 1], mn[j + (1 << (i - 1))][i - 1]);
			}
		}
	}
	/* RMQ */
	int rmq(int l, int r) {
		int k = log2(r - l + 1);
		return min(mn[l][k], mn[r + 1 - (1 << k)][k]);
	}
	int solve(int n, int l, int r, int k) {
		int pos = rank[l-1];
		int L = 1, R = pos;
		int ansL = pos, anaR = pos;
		while (L < R) {
			int mid = (L + R) / 2;
			if (rmq(mid, pos) >= r - l + 1) {
				R = mid;
			} else {
				L = mid + 1;
			}
		}
		if(rmq(L, pos) >= r - l + 1) {
			ansL = L - 1;
		}
		if(pos < n) {
			pos++;
			L = pos, R = n;
			while (L < R) {
				int mid = (L + R) / 2;
				if (rmq(pos, mid) >= r - l + 1) {
					L = mid + 1;
				} else {
					R = mid;
				}
			}
			if(rmq(pos, L) < r - l + 1) {
				L--;
			}
			if(L >= pos && rmq(pos, L) >= r - l + 1) {
				anaR = L;
			}
		}
		if(anaR - ansL + 1 < k) {
			return -1;
		}
		return query(rt[anaR], rt[ansL - 1], 0, maxn, k) + 1;
	}
} SA;

char s[maxn];
int ss[maxn];
int main() {
	int t;
	scanf("%d", &t);
	while(t--) {
		int n, q, l, r, k;
		scanf("%d %d", &n, &q);
		scanf("%s", s);
		for(int i = 0; i < n; i++) {
			ss[i] = s[i] - 'a' + 1;
		}
		ss[n] = 0;
		SA.build_sa(ss, n+1, 27);
		SA.getHeight(ss, n+1);
		SA.init(n+1);
		while(q--) {
			scanf("%d %d %d", &l, &r, &k);
			printf("%d\n", SA.solve(n, l, r, k));
		}
	}
	return 0;
}