分析
如果 $[l, r]$ 内不存在两个相同字符，则无解，否则答案至多为 $4$。
于是我们可以对答案进行讨论：
- 如果答案为 $1$，说明子串形如 $AAAA\cdots$，因此我们可以枚举 $r - l + 1$ 的约数 $d$，并判断其是否存在长度为 $d$ 的周期。
- 如果答案为 $2$，有三种情况：$AAB$、$ABA$、$BAA$。对于第一种和第三种，我们需要求以 $l$ 开头 / 以 $r$ 结尾的最短的 $AA$ 串，不妨设为 $L_l$ 和 $R_r$；对于第二种，我们需要判断 $ABA$ 是否存在 border。
- 如果答案为 $3$，有三种情况：$ABAC$、$BAAC$、$BACA$。对于第一种和第三种，显然 $A$ 取一个字符最好，因此我们只需要判断开头 / 结尾的字符是否出现了两次；对于第二种，我们需要判断 $[l, r]$ 中是否存在 $AA$ 串，即判断 $\min_{l \leq i \leq r} \{ L_i \}$ 是否 $\leq r$。
- 否则答案为 $4$。
下面考虑如何实现。
首先我们对于每种字符，求出其出现次数的前缀和，这样子就可以判断无解和 $ABAC$、$BACA$。
然后我们对原串求后缀数组，从而实现求两个后缀的 LCP，这样子就可以方便的判断周期。
我们还需要求出 $L_i$ 和 $R_i$，使用 NOI2016 优秀的拆分 中的方法，每次相当于一个区间对一个等差数列取 $\min$，可以使用线段树维护。这样子同时可以求出区间 $L_i$ 的最小值。
最后还剩下一个判断区间 border 的问题。有一个 $\mathcal{O}(\sqrt{n})$ 求出区间最短 border 的方法：首先判断是否有长度为 $1 \sim \sqrt{n}$ 的 border，如果没有，则最短 border 与原串的后缀排名差 $\leq \sqrt{n}$（证明略）。这样子可以做到 $\mathcal{O}(\sqrt{n})$ 的枚举量。
代码
// ====================================
// author: M_sea
// website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;
int read() {
int X = 0, w = 1; char c = getchar();
while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
return X * w;
}
const int N = 200000 + 10;
const int inf = 0x3f3f3f3f;
int n, Q; char s[N];
int sum[N][26];
struct SuffixArray {
int sa[N], rnk[N], height[N], x[N], y[N], z[N];
void SuffixSort() {
int m = 256;
for (int i = 1; i <= n; ++i) ++z[x[i] = s[i]];
for (int i = 2; i <= m; ++i) z[i] += z[i - 1];
for (int i = n; i; --i) sa[z[x[i]]--] = i;
for (int k = 1; k < n; k <<= 1) {
int p = 0;
for (int i = n - k + 1; i <= n; ++i) y[++p] = i;
for (int i = 1; i <= n; ++i) if (sa[i] > k) y[++p] = sa[i] - k;
for (int i = 1; i <= m; ++i) z[i] = 0;
for (int i = 1; i <= n; ++i) ++z[x[i]];
for (int i = 2; i <= m; ++i) z[i] += z[i - 1];
for (int i = n; i; --i) sa[z[x[y[i]]]--] = y[i], y[i] = 0;
swap(x, y), x[sa[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;
if (p == m) break;
m = p;
}
}
void GetHeight() {
for (int i = 1; i <= n; ++i) rnk[sa[i]] = i;
for (int i = 1, j = 0; i <= n; ++i) {
if (j) --j;
int p = sa[rnk[i] - 1];
while (s[i + j] == s[p + j]) ++j;
height[rnk[i]] = j;
}
}
int lg[N], st[18][N];
void buildST() {
for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
for (int i = 1; i <= n; ++i) st[0][i] = height[i];
for (int i = 1; i < 18; ++i)
for (int j = 1; j <= n; ++j)
st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
}
int qmin(int l, int r) {
int t = lg[r - l + 1];
return min(st[t][l], st[t][r - (1 << t) + 1]);
}
int LCP(int x, int y) {
if (rnk[x] > rnk[y]) swap(x, y);
return qmin(rnk[x] + 1, rnk[y]);
}
} A, B;
#define ls (o << 1)
#define rs (o << 1 | 1)
struct SegmentTree {
int minv[N << 2], tag[N << 2];
SegmentTree() { memset(minv, 0x3f, sizeof(minv)), memset(tag, 0x3f, sizeof(tag)); }
void update(int o, int l, int w) { tag[o] = min(tag[o], w), minv[o] = min(minv[o], l + w); }
void pushup(int o) { minv[o] = min(minv[ls], minv[rs]); }
void pushdown(int o, int l, int r) {
int mid = (l + r) >> 1;
if (tag[o] != inf) update(ls, l, tag[o]), update(rs, mid + 1, tag[o]), tag[o] = inf;
}
void modify(int o, int l, int r, int ql, int qr, int w) {
if (ql <= l && r <= qr) { update(o, l, w); return; }
int mid = (l + r) >> 1; pushdown(o, l, r);
if (ql <= mid) modify(ls, l, mid, ql, qr, w);
if (qr > mid) modify(rs, mid + 1, r, ql, qr, w);
pushup(o);
}
int query(int o, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return minv[o];
int mid = (l + r) >> 1, res = inf; pushdown(o, l, r);
if (ql <= mid) res = min(res, query(ls, l, mid, ql, qr));
if (qr > mid) res = min(res, query(rs, mid + 1, r, ql, qr));
return res;
}
} L, R;
#undef ls
#undef rs
void InitAA(SuffixArray &lcp_sa, SuffixArray &lcs_sa, SegmentTree &T) {
for (int l = 1; l <= n / 2; ++l)
for (int i = l, j = l << 1; j <= n; i += l, j += l) {
int lcp = lcp_sa.LCP(i, j), lcs = lcs_sa.LCP(n - i + 1, n - j + 1);
if (lcp + lcs - 1 >= l) T.modify(1, 1, n, i - lcs + 1, i + lcp - l, 2 * l - 1);
}
}
bool CheckBorder(int l, int r) {
int len = r - l + 1, S = sqrt(n) + 1;
for (int i = 1; i < len && i <= S; ++i)
if (A.LCP(l, r - i + 1) >= i) return 1;
for (int i = A.rnk[l] - 1, h = A.height[i + 1], c = 0; i && c <= S && h > S; ++c, h = min(h, A.height[i--]))
if (A.sa[i] >= l && A.sa[i] <= r && A.sa[i] + h > r) return 1;
for (int i = A.rnk[l] + 1, h = A.height[i], c = 0; i <= n && c <= S && h > S; ++c, h = min(h, A.height[++i]))
if (A.sa[i] >= l && A.sa[i] <= r && A.sa[i] + h > r) return 1;
return 0;
}
bool CheckNS(int l, int r) {
int flag = 1;
for (int i = 0; i < 26; ++i)
if (sum[r][i] - sum[l - 1][i] >= 2) { flag = 0; break; }
return flag;
}
bool Check1(int l, int r) {
int len = r - l + 1;
for (int i = 1; i * i <= len; ++i) {
if (len % i) continue;
if (A.LCP(l, l + i) >= len - i) return 1;
if (i != 1 && A.LCP(l, l + len / i) >= len - len / i) return 1;
}
return 0;
}
bool Check2(int l, int r) {
if (CheckBorder(l, r)) return 1;
if (L.query(1, 1, n, l, l) <= r) return 1;
if (R.query(1, 1, n, n - r + 1, n - r + 1) <= n - l + 1) return 1;
return 0;
}
bool Check3(int l, int r) {
if (sum[r][s[l] - 'a'] - sum[l][s[l] - 'a']) return 1;
if (sum[r - 1][s[r] - 'a'] - sum[l - 1][s[r] - 'a']) return 1;
if (L.query(1, 1, n, l, r) <= r) return 1;
return 0;
}
int main() {
n = read(); scanf("%s", s + 1);
for (int i = 1; i <= n; ++i)
for (int j = 0; j < 26; ++j)
sum[i][j] = sum[i - 1][j] + (j == s[i] - 'a');
A.SuffixSort(), A.GetHeight(), A.buildST();
reverse(s + 1, s + n + 1);
B.SuffixSort(), B.GetHeight(), B.buildST();
reverse(s + 1, s + n + 1);
InitAA(A, B, L), InitAA(B, A, R);
Q = read();
while (Q--) {
int l = read(), r = read();
if (CheckNS(l, r)) { puts("-1"); continue; }
if (Check1(l, r)) { puts("1"); continue; }
if (Check2(l, r)) { puts("2"); continue; }
if (Check3(l, r)) { puts("3"); continue; }
puts("4");
}
return 0;
}
3 条评论
6666字数瞩目
这是巧合（
艹你去写了这题啊 /fad