It's Mooin' Time III

题意

给定一个长度为 $N$ 的小写字母串。一个三元组 $(i,j,k)$ 合法，当且仅当：

$i<j<k$
$s_j=s_k$
$s_i\ne s_j$

也就是三个字符形如 abb，其中 a 和 b 不同。

每个询问给出区间 $[l,r]$ ，要求在 $l \leqslant i<j<k \leqslant r$ 中，最大化：

(j-i)(k-j)

如果不存在合法三元组，输出 -1。

思路

先看一个最直接的暴力写法：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 15:02
 * update_at: 2026-07-11 15:06
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n, q;
string s;

bool is_moo(int i, int j, int k) {
    return s[i] != s[j] && s[j] == s[k];
}

long long calc_value(int i, int j, int k) {
    return 1LL * (j - i) * (k - j);
}

long long brute_query(int l, int r) {
    long long ans = -1;

    // 小数据暴力：直接枚举所有 i < j < k。
    for (int i = l; i <= r; i++) {
        for (int j = i + 1; j <= r; j++) {
            for (int k = j + 1; k <= r; k++) {
                if (is_moo(i, j, k)) {
                    long long value = calc_value(i, j, k);
                    if (ans < value) ans = value;
                }
            }
        }
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    cin >> s;
    s = " " + s;

    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << brute_query(l, r) << '\n';
    }

    return 0;
}

这个暴力对每个查询枚举所有 $i<j<k$ ，完全按题意检查 s[i] s[j] s[k] 是否为 moo。它能帮助我们看清枚举对象，但复杂度是 $O(QN^3)$ ，无法通过满数据。

观察一个合法 moo 的形态是 abb。我们可以枚举重复字符 b。

固定 b 后， $i$ 必须是一个不是 b 的位置， $j,k$ 必须都是 b。为了让答案更大， $i$ 应该尽量靠左， $k$ 应该尽量靠右，因为这样会扩大 $(j-i)$ 和 $(k-j)$ 的可用空间。

于是对某个查询 $[l,r]$ 和某个字符 b：

text

1
2i = [l,r] 中最靠左的非 b
k = [l,r] 中最靠右的 b

确定 $i,k$ 后，只剩下选择 $j$ 。此时要最大化：

(j-i)(k-j)

这个乘积在 $j$ 靠近 $i$ 和 $k$ 的中点时最大。因此只需要检查中点左侧最近的 b 和中点右侧最近的 b。

为了快速得到这些位置，预处理三个数组：

left_pos[i][c]：1..i 中字符 c 的最右位置。
next_pos[i][c]：i..n 中字符 c 的最左位置。
next_not[i][c]：i..n 中第一个不是字符 c 的位置。

每次查询枚举 26 个重复字符，用这些数组常数时间找到 $i,k$ 和两个 $j$ 候选。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 15:02
 * update_at: 2026-07-11 15:06
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int C = 26;

int n, q;
string s;

int left_pos[MAXN][C]; // left_pos[i][c] 表示 1..i 中字符 c 最靠右的位置。
int next_pos[MAXN][C]; // next_pos[i][c] 表示 i..n 中字符 c 最靠左的位置。
int next_not[MAXN][C]; // next_not[i][c] 表示 i..n 中第一个不是字符 c 的位置。

long long calc_value(int i, int j, int k) {
    return 1LL * (j - i) * (k - j);
}

void build_precalc() {
    for (int c = 0; c < C; c++) {
        left_pos[0][c] = 0;
    }

    for (int i = 1; i <= n; i++) {
        for (int c = 0; c < C; c++) {
            left_pos[i][c] = left_pos[i - 1][c];
        }
        left_pos[i][s[i] - 'a'] = i;
    }

    for (int c = 0; c < C; c++) {
        next_pos[n + 1][c] = n + 1;
    }

    for (int i = n; i >= 1; i--) {
        for (int c = 0; c < C; c++) {
            next_pos[i][c] = next_pos[i + 1][c];
        }
        next_pos[i][s[i] - 'a'] = i;

        int best = n + 1;
        int second_best = n + 1;
        for (int c = 0; c < C; c++) {
            if (next_pos[i][c] < best) {
                second_best = best;
                best = next_pos[i][c];
            } else if (next_pos[i][c] < second_best) {
                second_best = next_pos[i][c];
            }
        }

        for (int c = 0; c < C; c++) {
            if (next_pos[i][c] == best) next_not[i][c] = second_best;
            else next_not[i][c] = best;
        }
    }
}

long long answer_query(int l, int r) {
    long long ans = -1;

    // 枚举 moo 的后两个相同字符。
    for (int rc = 0; rc < C; rc++) {
        int k = left_pos[r][rc];  // rc 在 [l,r] 中尽量靠右，作为第三个位置。
        int i = next_not[l][rc];  // 第一个不是 rc 的位置，作为第一个位置。

        if (i >= k) continue;

        int mid = (i + k) / 2;

        // j 越靠近 i 和 k 的中点，(j-i)(k-j) 越大。
        int j1 = left_pos[mid][rc];
        if (i < j1 && j1 < k) {
            long long value = calc_value(i, j1, k);
            if (ans < value) ans = value;
        }

        int j2 = next_pos[mid][rc];
        if (i < j2 && j2 < k) {
            long long value = calc_value(i, j2, k);
            if (ans < value) ans = value;
        }
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    cin >> s;
    s = " " + s;

    build_precalc();

    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << answer_query(l, r) << '\n';
    }

    return 0;
}

复杂度

预处理需要 $O(26N)$ 。

每个查询枚举 26 个字符，每个字符只做常数次位置查询，所以总时间复杂度为 $O(26(N+Q))$ 。

空间复杂度为 $O(26N)$ 。

总结

这题的关键是不要枚举三元组，而是枚举 moo 的重复字符。

固定重复字符后，两端位置有贪心选择：最左的非重复字符和最右的重复字符。中间位置再利用乘积在中点附近最大的性质，只检查两个最近候选即可。

目录

题意

思路

代码

复杂度

总结