原题链接
超毒瘤的一道题。
先想想如何比较在(S)的(i,j)前插入(T)组成的字符串的大小。不妨设(i<j)，两个字符串为(S_1,S_2)
首先(S_{0..i-1})和(S_{j..n-1})是不用管了，因为它们在(S_1,S_2)里面位置不变。剩下来的就是(S_{l..r-1})，设其为(s)。我们现在要比较的就是(s+T)和(T+s)。不妨设(|s|le|T|)，则要比较的是(3)部分：(s)和(T_{0..|s|-1})，(T_{|s|..|T|-1})和(T_{0..|T|-|s|-1})，(T_{|T|-|s|..|T|-1})和(s)。这珂以通过建立(S+T)的后缀数组来求。通过这个求出一个数组(p_i)，代表当把(T)插入到(S)的第(i)个元素前时的字符串的字典序排名。
接下来就处理询问的事情。
遇到这种在询问里有取模的限制，通常都是根号分治。这题也珂以这样。设块长为(B)。以下默认rmq为常用的ST表。
若(k>B)，则直接这个询问的范围所覆盖的连续区间不超过(dfrac{N}{B})个。这就珂以直接对于原(p)数组建立rmq，然后暴力查询即珂。这一部分时间复杂度为(O(dfrac{N^2}{B}+Nlog N))。
若(kle B)，则把询问离线。之后枚举模数mod，再枚举摸mod的余数r，对于所有的(imod mod=r)的(i)建立rmq，然后枚举询问，若(xle rle y)则通过计算算出这个询问在rmq上的左右端点后查询更新答案。这一部分的时间复杂度为(O(BN(log N+1))=O(BNlog N))。
取(B=N^{1-varphi})就能过(别问我为什么是这么奇怪的数字)。
代码：
// Code by H~$~C
#include <bits/stdc++.h>
using namespace std;
#define epoch_time chrono::steady_clock::now().time_since_epoch().count()
static mt19937 __gen(epoch_time);
#define random_shuffle(begin, end) shuffle(begin, end, __gen)
#define fi first
#define se second
#define x1 x1_19260817
#define y1 y1_19260817
#define j1 j1_19260817
#define x0 x0_19260817
#define y0 y0_19260817
#define j0 j0_19260817
#define left left_19260817
#define right right_19260817
#define rank rank_19260817
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
constexpr int inf = 0x3f3f3f3f;
constexpr ll lnf = 0x3f3f3f3f3f3f3f3f;
static const int Maxn = 100005;
static const int SQRT = 137;
static const int LOG = 20;
int n, m, q;
int ans[Maxn];
char s[Maxn << 1], t[Maxn];
int p[Maxn], id[Maxn];
struct Query {
int l, r, k, x, y, id;
Query() = default;
inline void read() {
scanf("%d%d%d%d%d", &l, &r, &k, &x, &y);
}
} qry[Maxn];
namespace suffix_array {
static const int Maxn = ::Maxn << 1;
int sa[Maxn], rnk[Maxn], height[Maxn], s[Maxn];
int wa[Maxn], wb[Maxn], wc[Maxn], wv[Maxn];
int ST[Maxn][LOG], LOG2[Maxn];
inline bool cmp_sa(int *y, int a, int b, int l) {
return y[a] == y[b] && y[a + l] == y[b + l];
}
template<typename T>
void build_SA(T *r, int n, int m) {
register int i, j, p;
int *x = wa, *y = wb, *t; ++n;
for (i = 0; i < n; ++i) s[i] = r[i];
for (i = 0; i < m; ++i) wc[i] = 0;
for (i = 0; i < n; ++i) wc[x[i] = s[i]]++;
for (i = 1; i < m; ++i) wc[i] += wc[i - 1];
for (i = n; ~--i; ) sa[--wc[x[i]]] = i;
for (p = 1, j = 1; p < n; j <<= 1, m = p) {
for (p = 0, 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 < n; ++i) wv[i] = x[y[i]];
for (i = 0; i < m; ++i) wc[i] = 0;
for (i = 0; i < n; ++i) wc[wv[i]]++;
for (i = 1; i < m; ++i) wc[i] += wc[i - 1];
for (i = n; ~--i; ) sa[--wc[wv[i]]] = y[i];
for (t = x, x = y, y = t, p = 1, x[*sa] = 0, i = 1; i < n; ++i)
x[sa[i]] = cmp_sa(y, sa[i], sa[i - 1], j) ? p - 1: p++;
}
for (i = 0; i < n; ++i) rnk[sa[i]] = i;
for (i = p = 0; i < n; height[rnk[i++]] = p)
for (p ? p-- : 0, j = sa[rnk[i] - 1]; s[i + p] == s[j + p]; p++);
LOG2[0] = -1;
for (int i = 1; i <= n; ++i)
LOG2[i] = LOG2[i >> 1] + 1, ST[i][0] = height[i];
for (int j = 1; j < LOG; ++j)
for (int i = 1; i + (1 << j) - 1 <= n; ++i)
ST[i][j] = min(ST[i][j - 1], ST[i + (1 << (j - 1))][j - 1]);
}
// sa[rank] = name, rnk[name] = rank
// height[i] = lcp(suffix(sa[i - 1]), suffix(sa[i]))
inline int query_ST(int l, int r) {
int k = LOG2[r - l + 1];
return min(ST[l][k], ST[r - (1 << k) + 1][k]);
}
inline int query_lcp(int l, int r) {
if (l == r) return inf;
l = rnk[l], r = rnk[r];
if (l > r) swap(l, r);
return query_ST(l + 1, r);
}
inline int cmp_substring(int l, int r, int len) {
if (query_lcp(l, r) >= len) return 0;
return rnk[l] < rnk[r] ? -1 : 1;
}
inline bool cmp_insert(int l, int r) {
bool is_swapped = false;
if (l > r) swap(l, r), is_swapped = true;
int t;
if (l + m <= r) {
t = cmp_substring(n, l, m);
if (t) return (t < 0) ^ is_swapped;
t = cmp_substring(l, l + m, r - (l + m));
if (t) return (t < 0) ^ is_swapped;
t = cmp_substring(r - m, n, m);
if (t) return (t < 0) ^ is_swapped;
}
else {
t = cmp_substring(n, l, r - l);
if (t) return (t < 0) ^ is_swapped;
t = cmp_substring(n + r - l, n, l + m - r);
if (t) return (t < 0) ^ is_swapped;
t = cmp_substring(l, n + l + m - r, r - l);
if (t) return (t < 0) ^ is_swapped;
}
return 1 ^ is_swapped;
}
}
using suffix_array::build_SA;
using suffix_array::cmp_insert;
int ST[Maxn][LOG], LOG2[Maxn];
template<typename Func>
inline void build_ST(int len, Func exact_key) {
LOG2[0] = -1;
for (int i = 1; i <= len; ++i) LOG2[i] = LOG2[i >> 1] + 1;
for (int i = 1; i <= len; ++i) ST[i][0] = exact_key(i);
for (int j = 1; j < LOG; ++j)
for (int i = 1; i + (1 << j) - 1 <= len; ++i)
ST[i][j] = min(ST[i][j - 1], ST[i + (1 << (j - 1))][j - 1]);
}
inline int query_ST(int l, int r) {
int k = LOG2[r - l + 1];
return min(ST[l][k], ST[r - (1 << k) + 1][k]);
}
signed main() {
scanf("%s%s%d", s, t, &q);
n = strlen(s);
m = strlen(t);
strcpy(s + n, t);
build_SA<char>(s, n + m, 128);
for (int i = 0; i <= n; ++i) p[i] = i;
sort(p, p + n + 1, cmp_insert);
for (int i = 0; i <= n; ++i) id[p[i]] = i;
// for (int i = 0; i <= n; ++i)
// fprintf(stderr, "p[%d] = %d, id[%d] = %d
", i, p[i], i, id[i]);
for (int i = 1; i <= q; ++i) ans[i] = inf;
for (int i = 1; i <= q; ++i) qry[i].read(), qry[i].id = i;
sort(qry + 1, qry + q + 1, [&](const Query &x, const Query &y)->bool{
return x.k < y.k;
});
// solve k >= SQRT
build_ST(n + 1, [&](int x){return id[x - 1];});
for (int i = 1; i <= q; ++i) {
if (qry[i].k < SQRT) continue;
for (int j = 0; j * qry[i].k <= n; ++j) {
int mn = max(j * qry[i].k + qry[i].x, qry[i].l) + 1;
int mx = min(j * qry[i].k + qry[i].y, qry[i].r) + 1;
if (mn > mx) continue;
ans[qry[i].id] = min(ans[qry[i].id], query_ST(mn, mx));
}
}
// solve k < SQRT
for (int i = 1, j = 1; i < SQRT && j <= q; ++i) {
if (i != qry[j].k) continue;
int ed = j;
// fprintf(stderr, "i = %d
", i);
while (ed <= q && qry[ed].k == i) ++ed;
for (int module = 0; module < i; ++module) {
int length = (n + 1) / i + (module <= n % i) + 1;
build_ST(length, [&](int x){return id[(x - 1) * i + module];});
// for (int k = 1; k <= length; ++k)
// fprintf(stderr, "ST[%d] = %d
", k, ST[k][0]);
for (int k = j; k < ed; ++k) {
if (qry[k].x > module || qry[k].y < module) continue;
int left = (qry[k].l - module + i - 1) / i + 1;
int right = (qry[k].r - module + i) / i;
if (left > right) continue;
ans[qry[k].id] = min(ans[qry[k].id], query_ST(left, right));
// fprintf(stderr, "id = %d, left = %d, right = %d
", qry[k].id, left, right);
}
}
j = ed;
}
for (int i = 1; i <= q; ++i)
printf("%d%c", ans[i] == inf ? -1 : p[ans[i]], "
"[i == q]);
return 0;
}