「一本通 4.2 例 3」与众不同

形式化题目

给定长度为 $N$ 的整数数组 $a[0 \dots N-1]$ ，给出 $M$ 次询问。每次询问给定区间 $[L, R]$ （下标从 $0$ 开始，若 $L > R$ 则保证为区间两端点），要求计算区间 $[L, R]$ 内最长的连续子数组长度，使得该子数组内的所有元素互不相同（即完美序列）。

正解

思路

1. 朴素想法与瓶颈

若对每次询问 $[L, R]$ 都在该区间内用双指针（滑动窗口）寻找最长无重复子区间，单次查询最坏需要 $O(R - L + 1)$ 的时间，处理 $M$ 次询问的总时间复杂度为 $O(N \cdot M)$ 。在 $N, M \leqslant 2 \times 10^5$ 的数据规模下必然超时。

由于数组是静态的，考虑预处理出数组内部每个位置的信息，从而支持快速回答区间查询。

2. 状态定义与单调性

对于数组中的任意右端点 $i \in [0, N-1]$ ：

定义 $start[i]$ 表示以 $i$ 结尾的最长无重复子区间的起始下标。
若记录元素 $a_i$ 上一次出现的下标为 $last[a_i]$ ，则为了保证不含重复元素，区间起点必须大于 $last[a_i]$ ，即至少为 $last[a_i] + 1$ ；同时由于 $i-1$ 结尾的无重复起点为 $start[i-1]$ ，以 $i$ 结尾的起点也绝不能小于 $start[i-1]$ 。
于是有状态转移方程：
$start[i] = \max(start[i-1], last[a_i] + 1)$
显然， $start[i]$ 随 $i$ 单调不降： $start[0] \leqslant start[1] \leqslant \dots \leqslant start[N-1]$ 。
定义 $f[i] = i - start[i] + 1$ ，即在整个序列中，以 $i$ 结尾的最长无重复子序列的完整长度。

3. 询问区间的拆分与二分

对于给定的询问区间 $[L, R]$ ，区间内的任意合法完美序列必然完全包含在 $[L, R]$ 内部。若固定该子序列的右端点为 $i \in [L, R]$ ，其合法的最左起点为 $\max(L, start[i])$ ：

当 $start[i] < L$ 时，原本能延伸到的左端点超出了询问边界，被限制在 $L$ 处，此时以 $i$ 结尾在 $[L, R]$ 内的最长长度为 $i - L + 1$ 。
当 $start[i] \geqslant L$ 时，最长无重复子区间完全落在 $[L, R]$ 内部，不受边界 $L$ 截断，此时以 $i$ 结尾的最长长度就是完整的 $f[i] = i - start[i] + 1$ 。

利用 $start$ 数组的单调递增性，可以在区间 $[L, R]$ 上进行二分查找，找到第一个满足 $start[mid] \geqslant L$ 的位置 $mid$ ：

左半部分 $i \in [L, mid - 1]$ ：所有 $start[i] < L$ 。对于这一段中的每个右端点 $i$ ，其最大长度为 $i - L + 1$ 。由于 $i - L + 1$ 随 $i$ 严格单调递增，该段的最大值必然在右端点 $i = mid - 1$ 处取得，最大值为 $(mid - 1) - L + 1 = mid - L$ 。
右半部分 $i \in [mid, R]$ ：所有 $start[i] \geqslant L$ 。对于这一段中的每个右端点 $i$ ，其最大长度就是 $f[i]$ 。因此该段的最大值为静态区间 $[mid, R]$ 上的 $f[i]$ 的最大值，即 $\max_{i=mid}^{R} f[i]$ 。

最终区间 $[L, R]$ 的答案即为：

\max(mid - L, \max_{i=mid}^{R} f[i])

（若不存在满足条件的 $mid$ ，即所有 $start[i] < L$ ，则说明整段区间 $[L, R]$ 无重复元素，答案直接为 $R - L + 1$ ）。

4. 区间最值查询（ST 表）

对于右半部分的区间最大值查询 $\max_{i=mid}^{R} f[i]$ ，由于数组 $f$ 是静态的，可以使用 ST 表（Sparse Table） 在 $O(N \log N)$ 预处理后，以 $O(1)$ 的时间复杂度查询任意区间的最大值。

可视化推演

以样例数组 a = [2, 5, 4, 1, 2, 3, 6, 2, 4] 为例，预处理得到的 $start$ 数组与 $f$ 数组如下表所示：

下标 $i$	0	1	2	3	4	5	6	7	8
元素 $a[i]$	2	5	4	1	2	3	6	2	4
$start[i]$	0	0	0	0	1	1	1	5	5
$f[i]$	1	2	3	4	4	5	6	3	4

对于询问 L = 0, R = 8：

第一个满足 $start[mid] \geqslant 0$ 的位置为 $mid = 0$ 。
左半部分为空，右半部分为整个区间 $[0, 8]$ 的 $\max f[i] = 6$ 。

对于询问 L = 2, R = 6：

第一个满足 $start[mid] \geqslant 2$ 的位置在区间 $[2, 6]$ 内不存在（ $start[6]=1 < 2$ ），即整段区间内的元素互不重复。
答案即为区间长度 $6 - 2 + 1 = 5$ 。

代码

Python 版：

python

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#!/usr/bin/env python3
# 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-09-30 17:25
# update_at: 2026-09-30 17:25

import bisect
import sys


def build_st_table(arr: list[int]) -> tuple[list[int], list[list[int]]]:
    """构建区间最大值 ST 表，返回 (log2 预处理表, ST 倍增二维表)。"""
    n = len(arr)
    log_table = [0] * (n + 1)
    for i in range(2, n + 1):
        log_table[i] = log_table[i >> 1] + 1

    st: list[list[int]] = [arr[:]]
    k = log_table[n]
    for j in range(1, k + 1):
        prev = st[j - 1]
        half = 1 << (j - 1)
        st.append([
            max(prev[i], prev[i + half])
            for i in range(n - (1 << j) + 1)
        ])
    return log_table, st


def range_max(st: list[list[int]], log_table: list[int], left: int, right: int) -> int:
    """查询区间 [left, right] 上的最大值。"""
    k = log_table[right - left + 1]
    return max(st[k][left], st[k][right - (1 << k) + 1])


def answer_query(
    left: int,
    right: int,
    start: list[int],
    st: list[list[int]],
    log_table: list[int],
) -> int:
    """计算区间 [left, right] 内最长完美序列长度。"""
    if left > right:
        left, right = right, left

    # 二分找到第一个 start[i] >= left 的位置 mid
    mid = bisect.bisect_left(start, left, left, right + 1)
    left_part = mid - left  # 左半段以 left 为起点的最大长度为 mid - left
    right_part = range_max(st, log_table, mid, right) if mid <= right else 0
    return max(left_part, right_part)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    m = next(data)
    a = [next(data) for _ in range(n)]

    # 预处理每个位置 i 作为右端点时，最左能延伸到的无重复起点 start[i]
    start = [0] * n
    last_pos: dict[int, int] = {}
    for i, val in enumerate(a):
        prev_pos = last_pos.get(val, -1) + 1
        start[i] = max(start[i - 1] if i > 0 else 0, prev_pos)
        last_pos[val] = i

    f = [i - start[i] + 1 for i in range(n)]
    log_table, st = build_st_table(f)

    ans: list[int] = []
    for _ in range(m):
        l = next(data)
        r = next(data)
        ans.append(answer_query(l, r, start, st, log_table))

    sys.stdout.write("\n".join(map(str, ans)) + "\n")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-10-05 07:19
 * update_at: 2026-10-05 07:19
 */
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 200005;         // 序列长度上界
const int MAXV = 2000005;        // 盈利值 a[i] 落在 [-1e6, 1e6]，平移后统一存到该数组
const int LOGN = 19;             // 2^18 > 2e5，倍增层数最多 18 层（0..17），开 19 保险

ll n, m;                         // 月份数、询问次数
int a[MAXN];                     // a[i] 表示第 i 个月的盈利值
int last_pos[MAXV];              // last_pos[v] 表示值 v 上一次出现的位置，没出现过为 -1
int start_pos[MAXN];             // start_pos[i] 表示以 i 结尾的最长无重复区间的起始下标
int f[MAXN];                     // f[i] = i - start_pos[i] + 1，即以 i 结尾的完整无重复长度
int log2_table[MAXN];            // log2_table[x] = floor(log2(x))，供 ST 表 O(1) 查询使用
int st[LOGN][MAXN];              // st[k][i] 表示从 i 开始长度为 2^k 的区间内 f 的最大值
                                 // f 的值不超过 N = 2e5，用 int 存足够

// 预处理 start_pos、f 以及区间最大值 ST 表。
void build() {
    for (int i = 0; i < MAXV; i++) {
        last_pos[i] = -1;
    }
    for (ll i = 0; i < n; i++) {
        int v = a[i] + 1000000;              // 平移值域到非负下标
        int cur = last_pos[v] + 1;           // 起点至少要越过上一次出现的位置
        if (i > 0 && start_pos[i - 1] > cur) {
            cur = start_pos[i - 1];          // 也不能小于上一位置的起点，保证单调不降
        }
        start_pos[i] = cur;
        last_pos[v] = i;
        f[i] = i - start_pos[i] + 1;
    }
    // log2 预处理
    log2_table[1] = 0;
    for (int i = 2; i <= n; i++) {
        log2_table[i] = log2_table[i / 2] + 1;
    }
    // ST 表第一层就是 f 本身，之后按长度倍增合并
    for (ll i = 0; i < n; i++) {
        st[0][i] = f[i];
    }
    for (int k = 1; (1 << k) <= n; k++) {
        int half = 1 << (k - 1);
        for (ll i = 0; i + (1 << k) <= n; i++) {
            st[k][i] = max(st[k - 1][i], st[k - 1][i + half]);
        }
    }
}

// 查询区间 [left, right] 上 f 的最大值。
int range_max(int left, int right) {
    int k = log2_table[right - left + 1];
    int v1 = st[k][left];
    int v2 = st[k][right - (1 << k) + 1];
    return v1 > v2 ? v1 : v2;
}

// 回答一次询问区间 [L, R] 内最长完美序列的长度。
int query(int L, int R) {
    // start_pos 单调不降，二分出第一个 start_pos[mid] >= L 的位置
    int lo = L;
    int hi = R + 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (start_pos[mid] >= L) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    int mid = lo;
    // 左半段 [L, mid-1] 内每个 i 都受 L 截断，最大值在 i = mid-1 处，为 mid - L
    int ans_left = mid - L;
    // 右半段 [mid, R] 内不截断，取 f 的区间最大值
    int ans_right = 0;
    if (mid <= R) {
        ans_right = range_max(mid, R);
    }
    return ans_left > ans_right ? ans_left : ans_right;
}

int main() {
    scanf("%lld%lld", &n, &m);
    for (ll i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    build();
    for (ll i = 0; i < m; i++) {
        int L, R;
        scanf("%d%d", &L, &R);
        if (L > R) {
            int tmp = L;
            L = R;
            R = tmp;
        }
        printf("%d\n", query(L, R));
    }
    return 0;
}

复杂度

时间复杂度：
- 预处理 $start$ 和 $f$ 数组：只需线性扫描一遍数组，耗时 $O(N)$ 。
- 构建 ST 表：倍增预处理区间最大值，耗时 $O(N \log N)$ 。
- 每次询问：二分查找分界点 $mid$ 耗时 $O(\log N)$ ，ST 表查询静态区间最值耗时 $O(1)$ 。
- 总时间复杂度为 $O(N \log N + M \log N)$ ，在极限数据规模下运算次数约为 $4 \times 10^6$ ，能轻松在时限内运行完成。
空间复杂度：
- ST 表二维数组大小为 $N \times (\lfloor \log_2 N \rfloor + 1)$ ，辅助数组占 $O(N)$ 空间。
- 总空间复杂度为 $O(N \log N)$ ，在 $128\text{ MB}$ 空间限制以内。

总结

本题的关键在于将静态区间的完美序列最值问题分解为两部分：

观察到每个位置无重复起点的单调性，从而能通过二分定位截断点 $mid$ 。
截断点左侧长度严格递增、单调取端点；截断点右侧不受边界限制，转化为经典的静态区间 RMQ 问题，使用 ST 表实现 $O(1)$ 查询。二分与 ST 表的高效配合将单次询问降低至 $O(\log N)$ 。