Description：
1<=n<=5e4
题解：
考虑\(f\)这个东西应该是怎样算的？
不妨建出SA，然后按height从大到小启发式合并，显然只有相邻的才可能成为最优答案。这样的只有\(O(n log n)\)个有用的串。
建SAM在fail树上启发式合并是一样的。
然后用个主席树就可以快速查询答案。
现在思考查询一个[x,y]，要求f>=z怎么办？
考虑一个区间[l,r]，如果a[l-1]<=max[a[l..r]]或a[r+1]<=max[a[l..r]]显然延伸会使f更大，而a不会更大。
这样从每个点开始造区间，就能造出n个区间，答案显然是这些区间中的一个。
不过有个问题，就是可能这些区间过长出界了，注意出界的话一定有一个端点是x或者y，可以二分+主席树查询。
后面看上去也要一个三维偏序，实际上不用，假设二分出来最左的y'使f[x,y']>=z，和最右的x'使f[x',y]>=z,那么只用查询l∈[x,x']或者r∈[y',y]的那些区间，这样就变成了二维偏序。
Code：
#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, B = y; i <= B; i ++)
#define ff(i, x, y) for(int i = x, B = y; i < B; i ++)
#define fd(i, x, y) for(int i = x, B = y; i >= B; i --)
#define ll long long
#define pp printf
#define hh pp("\n")
using namespace std;
const int N = 5e4 + 5;
int n, m;
char s[N];
int a[N];
struct SA {
int rk[N], sa[N], he[N], tx[N], tp[N], m;
void rsort() {
fo(i, 1, m) tx[i] = 0;
fo(i, 1, n) tx[rk[tp[i]]] ++;
fo(i, 1, m) tx[i] += tx[i - 1];
fd(i, n, 1) sa[tx[rk[tp[i]]] --] = tp[i];
}
int cmp(int *f, int x, int y, int z) { return f[x] == f[y] && f[x + z] == f[y + z];}
void build() {
s[0] = s[n + 1] = -1; tp[n + 1] = 0;
fo(i, 1, n) rk[i] = s[i], tp[i] = i;
m = 127; rsort();
for(int w = 1, p = 0; p < n; m = p, w *= 2) {
p = 0; fo(i, n - w + 1, n) tp[++ p] = i;
fo(i, 1, n) if(sa[i] > w) tp[++ p] = sa[i] - w;
rsort();
fo(i, 1, n) tp[i] = rk[i];
rk[sa[1]] = p = 1;
fo(i, 2, n) rk[sa[i]] = cmp(tp, sa[i - 1], sa[i], w) ? p : ++ p;
}
int j, k = 0;
for(int i = 1; i <= n; he[rk[i ++]] = k)
for(k ? k -- : 0, j = sa[rk[i] - 1]; s[j + k] == s[i + k]; k ++);
// fo(i, 1, n) {
// fo(j, sa[i], n) pp("%c", s[j]);
// pp(" %d\n", he[i]);
// }
}
} suf;
struct P {
int x, y, z;
} d[N * 40]; int d0;
namespace make_d {
multiset<int> s[N];
multiset<int> :: iterator it;
int f[N], t[N];
int F(int x) { return f[x] == x ? x : (f[x] = F(f[x]));}
int cmp(int x, int y) { return suf.he[x] > suf.he[y];}
void ins(int x, multiset<int> &s, int z) {
if(*s.begin() < x) d[++ d0] = (P) {*(--s.lower_bound(x)), x, z};
if(*s.rbegin() > x) d[++ d0] = (P) {x, *s.upper_bound(x), z};
}
void build() {
fo(i, 1, n) f[i] = i, s[i].insert(suf.sa[i]);
fo(i, 2, n) t[++ t[0]] = i;
sort(t + 1, t + n, cmp);
fo(i, 1, n - 1) {
int x = t[i] - 1, y = t[i];
x = F(x), y = F(y);
if(x != y) {
if(s[x].size() > s[y].size()) swap(x, y);
for(it = s[x].begin(); it != s[x].end(); it ++) {
ins(*it, s[y], suf.he[t[i]]);
}
for(it = s[x].begin(); it != s[x].end(); it ++)
s[y].insert(*it);
s[x].clear();
f[x] = y;
}
}
}
}
int cmp_d(P a, P b) { return a.x > b.x;}
struct tree {
int l, r, x, y;
} t[N * 400];
#define i0 t[i].l
#define i1 t[i].r
int tot, pl, pr, pc, px, g[N];
void upd(int i) {
t[i].x = max(t[i0].x, t[i1].x);
t[i].y = max(t[i0].y, t[i1].y);
}
void add(int &i, int x, int y) {
t[++ tot] = t[i]; i = tot;
if(x == y) {
if(!pc) {
t[i].x = max(t[i].x, px);
} else {
t[i].y = max(t[i].y, px);
}
return;
}
int m = x + y >> 1;
if(pl <= m) add(i0, x, m); else add(i1, m + 1, y);
upd(i);
}
void ft(int i, int x, int y) {
if(y < pl || x > pr || !i) return;
if(x >= pl && y <= pr) {
// pp("%d %d %d %d %d\n", x, y, t[i].x, t[i].y, pc);
if(!pc) px = max(px, t[i].x); else px = max(px, t[i].y);
return;
}
int m = x + y >> 1;
ft(i0, x, m); ft(i1, m + 1, y);
}
void make_tree() {
t[0].x = t[0].y = -1e9;
sort(d + 1, d + d0 + 1, cmp_d);
int l = 1;
fd(i, n, 1) {
g[i] = g[i + 1];
while(l <= d0 && d[l].x >= i) {
if(d[l].z > 0) {
// pp("%d %d %d %d\n", i, d[l].x, d[l].y, d[l].z);
pl = pr = d[l].y + d[l].z - 1;
pc = 0; px = d[l].z;
add(g[i], 1, n);
pl = pr = d[l].y + d[l].z - 1;
pc = 1; px = -d[l].y + 1;
add(g[i], 1, n);
}
l ++;
}
}
// fo(i, 1, d0) pp("%d %d %d\n", d[i].x, d[i].y, d[i].z); hh;
}
int query(int x, int y) {
pl = x; pr = y; px = -1e9; pc = 0;
ft(g[x], 1, n);
int ans = px;
pl = y; pr = n; px = -1e9; pc = 1;
ft(g[x], 1, n);
ans = max(ans, y + px);
return ans;
}
namespace tr {
struct tree {
int l, r, x, y;
} t[N * 40];
#define i0 t[i].l
#define i1 t[i].r
int tot, pl, pr, pc, px, rt;
void upd(int i) {
t[i].x = min(t[i0].x, t[i1].x);
t[i].y = min(t[i0].y, t[i1].y);
}
void add(int &i, int x, int y) {
if(!i) t[++ tot] = t[0], i = tot;
if(x == y) {
if(!pc) {
t[i].x = min(t[i].x, px);
} else {
t[i].y = min(t[i].y, px);
}
return;
}
int m = x + y >> 1;
if(pl <= m) add(i0, x, m); else add(i1, m + 1, y);
upd(i);
}
void ft(int i, int x, int y) {
if(y < pl || x > pr || !i) return;
if(x >= pl && y <= pr) {
if(!pc) px = min(px, t[i].x); else px = min(px, t[i].y);
return;
}
int m = x + y >> 1;
ft(i0, x, m); ft(i1, m + 1, y);
}
void xiu(int x, int y, int z) {
pl = pr = x; px = y; pc = z;
add(rt, 1, n);
}
int find(int x, int y, int z) {
px = 1e9; pl = x, pr = y; pc = z;
ft(rt, 1, n);
return px;
}
}
int f[17][N];
int qam(int x, int y) {
int l = log2(y - x + 1);
return max(f[l][x], f[l][y - (1 << l) + 1]);
}
int l[N], r[N], v[N], ti[N], z[N], z0;
int p[N], p0;
int cmp_p(int x, int y) { return ti[x] > ti[y];}
void make_dkl() {
fo(i, 1, n) f[0][i] = a[i];
fo(j, 1, 16) fo(i, 1, n) f[j][i] = max(f[j - 1][i], f[j - 1][i + (1 << j - 1)]);
fo(i, 1, n) l[i] = 1, r[i] = n;
z0 = 0;
fo(i, 1, n) {
while(z0 > 0 && a[z[z0]] <= a[i]) z0 --;
if(z0 > 0) l[i] = z[z0] + 1;
z[++ z0] = i;
}
z0 = 0;
fd(i, n, 1) {
while(z0 > 0 && a[z[z0]] <= a[i]) z0 --;
if(z0 > 0) r[i] = z[z0] - 1;
z[++ z0] = i;
}
tr :: t[0].x = tr :: t[0].y = 1e9;
fo(i, 1, n) v[i] = qam(l[i], r[i]), ti[i] = query(l[i], r[i]), p[i] = i;
sort(p + 1, p + n + 1, cmp_p);
}
int ans[N];
struct ask {
int x, y, z, i;
int as1, as2;
} q[N];
int cmp_q(ask a, ask b) { return a.z > b.z;}
void Ask() {
fo(i, 1, m) {
int x, y, z;
scanf("%d %d %d", &q[i].x, &q[i].y, &q[i].z);
q[i].i = i;
x = q[i].x, y = q[i].y, z = q[i].z;
int as1 = -1, as2 = -1;
for(int l = x, r = y; l <= r; ) {
int m = l + r >> 1;
if(query(x, m) >= z) as1 = m, r = m - 1; else l = m + 1;
}
if(as1 == -1) ans[i] = -1;
for(int l = x, r = y; l <= r; ) {
int m = l + r >> 1;
if(query(m, y) >= z) as2 = m, l = m + 1; else r = m - 1;
}
if(as1 != -1) ans[i] = min(qam(x, as1), qam(as2, y));
q[i].as1 = as1; q[i].as2 = as2;
}
sort(q + 1, q + m + 1, cmp_q);
int w = 1;
fo(i, 1, m) {
while(w <= n && ti[p[w]] >= q[i].z) {
tr :: xiu(l[p[w]], v[p[w]], 0);
tr :: xiu(r[p[w]], v[p[w]], 1);
w ++;
}
if(q[i].as1 != -1) {
ans[q[i].i] = min(ans[q[i].i], tr :: find(q[i].x, q[i].as2, 0));
ans[q[i].i] = min(ans[q[i].i], tr :: find(q[i].as1, q[i].y, 1));
}
}
fo(i, 1, m) pp("%d\n", ans[i]);
}
int main() {
freopen("string.in", "r", stdin);
freopen("string.out", "w", stdout);
scanf("%d %d", &n, &m);
scanf("%s", s + 1);
fo(i, 1, n) scanf("%d", &a[i]);
suf.build();
make_d :: build();
make_tree();
make_dkl();
Ask();
}