Description
给出一个字符串 \(S\)。
给出 \(Q\) 个操作，给出 \(L, R, T\)，求字典序最小的 \(S_1\)，使得 \(S^\prime\) 为\(S[L..R]\) 的子串，且 \(S^\prime\) 的字典序严格大于 \(T\)。输出这个 \(S^\prime\) ，如果无解输出 -1。
Hint
- \(1\le |S|\le 10^5\)
- \(1\le Q\le 2\times 10^5\)
- \(1\le L\le R\le |S|\)
- \(1\le \sum |T| \le 2\times 10^5\)
Solution
看到各种“子串”，考虑 SAM。
要求“字典序严格大于 \(T\) 的字典序最小子串”，那么有一个 贪心 的方法：找一个 \(T\) 的 前缀，后面加一个字典序稍大的字符。
这样的话直接把 \(T\) 放到 \(S\) 的 SAM 上跑，求出 每一位如果替换掉的话可以换的最小字符 \(\text{dir}\)。没有的话就是 \(-1\)。
然后整出 \(\text{dir}\) 之后，倒着 看看有没有 \(\text{dir}\ne -1\) 的位置，有就换掉这一位然后输出，否则答案就是 -1。
注意答案长度可能会比 \(T\) 大一，所以 \(\text{dir}\) 要算到 \(|T| + 1\) 位。
还有一个问题，就是怎么处理区间限制？
这就需要 \(\text{end-pos}\) 了。我指 处理出整个集合。 可以用树上主席树或线段树合并维护。这样可以快速判断 \(\text{end-pos}\) 中 是否含有某个区间中的值。 这样在用 \(T\) 在 SAM 上跑的时候就可以只走区间中的点，替换字符也可以只换可以到达区间中的点。
时空复杂度 \(O(n\log n)\)，这里将 \(\Sigma = 26\) 记为常数。
Code
实现比较复杂，注意细节。
线段树合并。
/*
* Author : _Wallace_
* Source : https://www.cnblogs.com/-Wallace-/
* Problem : Codeforces 1037H Security
*/
#include <iostream>
#include <map>
#include <string>using namespace std;
const int Len = 1e5 + 5;namespace segt {
const int S = Len << 6;
int lc[S], rc[S];
int total = 0;#define mid ((l + r) >> 1)
void insert(int& x, int p, int l = 1, int r = Len) {
if (!x) x = ++total;
if (l == r) return;
if (p <= mid) insert(lc[x], p, l, mid);
else insert(rc[x], p, mid + 1, r);
}
int merge(int x, int y, int l = 1, int r = Len) {
if (l == r || !x || !y) return x | y;
int z = ++total;
lc[z] = merge(lc[x], lc[y], l, mid);
rc[z] = merge(rc[x], rc[y], mid + 1, r);
return z;
}
bool find(int u, int v, int x, int l = 1, int r = Len) {
if (!x) return false;
if (u <= l && r <= v) return true;
if (u <= mid && find(u, v, lc[x], l, mid)) return true;
if (v > mid && find(u, v, rc[x], mid + 1, r)) return true;
return false;
}
};namespace SAM {
const int T = Len << 1;
struct Node {
map<char, int> ch;
int link, len, eprt;
} t[T];int total;
int last;void extend_char(char c) {
int p = last, np = last = ++total;
t[np].len = t[p].len + 1;for (; p && !t[p].ch[c]; p = t[p].link)
t[p].ch[c] = np;if (!p) {
t[np].link = 1;
} else {
int q = t[p].ch[c];
if (t[p].len + 1 == t[q].len) {
t[np].link = q;
} else {
int nq = ++total;
t[nq] = t[q], t[nq].len = t[p].len + 1;
t[np].link = t[q].link = nq;
for (; p && t[p].ch[c] == q; p = t[p].link)
t[p].ch[c] = nq;
}
}segt::insert(t[np].eprt, t[np].len);
}int b[T], c[T];
void topo_sort() {
for (register int i = 1; i <= total; i++) ++c[t[i].len];
for (register int i = 1; i <= total; i++) c[i] += c[i - 1];
for (register int i = 1; i <= total; i++) b[c[t[i].len]--] = i;
}void init_end_pos() {
for (register int i = total; i; i--) {
int x = b[i], f = t[x].link;
if (f) t[f].eprt = segt::merge(t[x].eprt, t[f].eprt);
}
}void init_data(string& s) {
total = last = 1;
for (string::iterator it = s.begin(); it != s.end(); it++)
extend_char(*it);topo_sort();
init_end_pos();
}int dir[Len];
string query(int l, int r, string str);
};string SAM::query(int l, int r, string str) {
int x = 1, y, i;
for (i = 1; ; i++) {
dir[i] = -1;char c = (i > str.size()) ? 'a' : str[i - 1] + 1;
map<char, int>::iterator it = t[x].ch.lower_bound(c);
for (; it != t[x].ch.end(); it++) {
y = it->second;
if (segt::find(l + i - 1, r, t[y].eprt)) {
dir[i] = it->first;
break;
}
}c = (i > str.size()) ? 0 : str[i - 1];
y = t[x].ch[c];
if (!y || i == str.size() + 1 || !segt::find(l + i - 1, r, t[y].eprt))
break;
x = y;
}for (; i && dir[i] == -1; i--);
if (!i) return "-1";string ret;
for (register int j = 1; j < i; j++)
ret += str[j - 1];
ret += dir[i];
return ret;
}signed main() {
ios::sync_with_stdio(false);string str;
cin >> str;
SAM::init_data(str);int q;
cin >> q;
while (q--) {
int L, R;
cin >> L >> R >> str;
cout << SAM::query(L, R, str) << '\n';
}return 0;
}
