Border的四种求法
为什么没有 SA 题解？气抖冷
提供一篇 SA + 树套树的做法。
对于一组询问
考虑单调栈，对于每个
比较这段区间割裂开后两端长度的大小。我们暴力进行小的那一边的所有修改与询问操作，复杂度分析同启发式合并。那么询问就是求另一侧关于某个数的前驱，修改就是另一侧的矩形加。
另一侧的矩形加可以使用树状数组套 multiset，另一侧关于 x 的前驱可以建立可持久化线段树后二分。综上，我们在
#include <bits/stdc++.h>
using namespace std;
const int N = 300010;
char s[N];
int q, n;
int sa[N], rk[N], height[N];
int l[N], r[N];
void SA(int m = 255) {
static int cnt[N], x[N], y[N];
for (int i = 1; i <= m; ++i) cnt[i] = 0;
for (int i = 1; i <= n; ++i) ++cnt[x[i] = s[i]];
for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; --i) sa[cnt[x[i]]--] = i;
int p = 1;
for (int k = 1; k <= n; k <<= 1) {
int cur = 0;
for (int i = n - k + 1; i <= n; ++i) y[++cur] = i;
for (int i = 1; i <= n; ++i) if (sa[i] > k) y[++cur] = sa[i] - k;
for (int i = 1; i <= m; ++i) cnt[i] = 0;
for (int i = 1; i <= n; ++i) ++cnt[x[i]];
for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; --i) sa[cnt[x[y[i]]]--] = y[i];
swap (x, y); x[sa[1]] = 1; p = 1;
for (int i = 2; i <= n; ++i)
x[sa[i]] = ((y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k]) ? p : ++p);
m = p;
}
memcpy (rk, x, sizeof (x));
}
void heihei() {
for (int i = 1, k = 0; i <= n; ++i) {
if (rk[i] == 1) continue;
if (k) --k;
int j = sa[rk[i] - 1];
while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) ++k;
// cerr << "LCP " << sa[rk[i] - 1] << " " << i << " = " << k << '\n';
height[rk[i]] = k;
}
}
int S[N];
struct node {
int first, second, id;
node(int first = 0, int second = 0, int id = 0):first(first), second(second), id(id){}
bool operator < (const node& t) const {return rk[first] < rk[t.first];}
}t[N];
vector<pair<int, int> > add[N], del[N];
int ans[N], root[N], ed[N];
struct persistent_sg {
int num[N * 20], ls[N * 20], rs[N * 20];
int cnt = 0;
void update(int& p, int o, int v, int l = 0, int r = n + 1) {
p = ++cnt;
num[p] = num[o] + 1;
ls[p] = ls[o]; rs[p] = rs[o];
if (l == r) return ;
int mid = (l + r) >> 1;
if (v <= mid) update (ls[p], ls[o], v, l, mid);
else update (rs[p], rs[o], v, mid + 1, r);
}
int qnum(int p, int q, int L, int R, int l = 0, int r = n + 1) {
if (L <= l && r <= R) return num[q] - num[p];
int mid = (l + r) >> 1, ret = 0;
if (L <= mid) ret += qnum(ls[p], ls[q], L, R, l, mid);
if (R > mid) ret += qnum(rs[p], rs[q], L, R, mid + 1, r);
return ret;
}
int big(int L, int R, int v) {
int ql = v, qr = n, ans = -1;
while (ql <= qr) {
int mid = (ql + qr) >> 1;
if (qnum(root[L - 1], root[R], v, mid)) ans = mid, qr = mid - 1;
else ql = mid + 1;
}
return ans;
}
}tr;
int twist(int x) {return 2 * n - x + 1;}
multiset<int> c[N << 1];
void Insert(int x, int val) {
for (; x <= 2 * n; x += x & -x)
c[x].insert(val);
}void Delete(int x, int val) {
for (; x <= 2 * n; x += x & -x)
c[x].erase(c[x].find(val));
}
int query(int x, int val) {
int an = 0x3f3f3f3f;
for (; x; x -= x & -x) {
auto p = c[x].lower_bound(val);
if (p != c[x].end()) an = min(an, (*p));
}
return an;
}
int main() {
scanf ("%s%d", s + 1, &q);
n = strlen(s + 1);
SA();
heihei();
for (int i = 1; i <= q; ++i)
scanf ("%d%d", &t[i].first, &t[i].second), S[rk[t[i].first]]++, t[i].id = i,ans[i] = 0x3f3f3f3f, ed[i] = t[i].second;
for (int i = 1; i <= n; ++i)
S[i] += S[i - 1];
sort (t + 1, t + 1 + q);
stack<int> stk;
for (int i = 2; i <= n; ++i) l[i] = 1, r[i] = n + 1;
for (int i = 2; i <= n; ++i) {
while (!stk.empty() && height[stk.top()] >= height[i]) stk.pop();
if (!stk.empty()) l[i] = stk.top();
stk.push(i);
}
while (!stk.empty()) stk.pop();
for (int i = n; i >= 2; --i) {
while (!stk.empty() && height[stk.top()] > height[i]) stk.pop();
if (!stk.empty()) r[i] = stk.top();
stk.push(i);
}
for (int i = 1; i <= n; ++i)
tr.update(root[i], root[i - 1], sa[i]);
for (int i = 2; i <= n; ++i) {
++l[i], --r[i];
if (i - l[i] + S[i - 1] - S[l[i] - 2] > r[i] - i + S[r[i]] - S[i - 1]) {
int pos = lower_bound(t + 1, t + q + 1, node(sa[i], 0, 0)) - t;
for (int j = i; j <= r[i]; ++j) {
int id = sa[j];
add[l[i] - 1].push_back({height[i] + id - 1, id});
del[i].push_back({height[i] + id - 1, id});
}
while (pos <= q && rk[t[pos].first] <= r[i]) {
int L = t[pos].first, R = t[pos].second;
int val = tr.big(l[i] - 1, i - 1, max(L, R - height[i] + 1));
if (val != -1 && val <= R) ans[t[pos].id] = min(ans[t[pos].id], val);
++pos;
}
} else {
int pos = lower_bound(t + 1, t + q + 1, node(sa[l[i] - 1], 0, 0)) - t;
for (int j = l[i] - 1; j < i; ++j) {
int id = sa[j];
add[i].push_back({height[i] + id - 1, id});
del[r[i] + 1].push_back({height[i] + id - 1, id});
}
while (pos <= q && rk[t[pos].first] < i) {
int L = t[pos].first, R = t[pos].second;
int val = tr.big(i, r[i], max(L, R - height[i] + 1));
if (val != -1 && val <= R) ans[t[pos].id] = min(ans[t[pos].id], val);
++pos;
}
}
}
int p = 1;
for (int i = 1; i <= n; ++i) {
for (auto e: add[i]) {
int R = twist(e.first);
Insert(R, e.second);
}
for (auto e: del[i]) {
int R = twist(e.first);
Delete(R, e.second);
}
while (p <= q && rk[t[p].first] == i) {
ans[t[p].id] = min(ans[t[p].id], query(twist(t[p].second), t[p].first));
++p;
}
}
for (int i = 1; i <= q; ++i) {
if (ans[i] == 0x3f3f3f3f || ed[i] - ans[i] + 1 < 0) printf("0\n");
else printf("%d\n", ed[i] - ans[i] + 1);
}
return 0;
}