思路与算法

从左到右求 b[i]：以i为右端点的最长不重复后缀的左端点，并令 g[i]=i-b[i]+1。遇到重复数时，用它上次出现的位置抬高左边界，所以b单调不降。对g建最大值ST表。查询 [L,R] 时，二分找第一个满足 b[p]>L 的位置p；若不存在，令p=R+1。答案是 p-L 与 g[p..R] 最大值中的较大者。

正确性说明

在p之前，b[i]≤L，所以 [L,i] 本身没有重复；这一段的最优长度随i增加，在p-1处达到p-L。从p开始，b[i]>L，全局最长不重复后缀已经完全处于查询内部，以i结尾的最优答案就是g[i]。两部分覆盖全部可能的右端点，取最大值即可得到整个区间的最优长度。

复杂度

设值域长度 V=2000001，本实现初始化上次出现位置需要 O(V)。总时间 O(V+N log N+M log N)，空间 O(V+N log N)。每次二分 O(log N)，ST查询 O(1)。

易错点

输入编号从0开始，不要按1开始解析。不能直接查询g[L..R]的最大值，因为有的后缀会越过L。分界使用b[p]>L；不存在分界时，整个查询区间都是完美序列。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> left(n), len(n), last(2000001, -1), lg(n + 1);
    int l = 0;
    for (int i = 0; i < n; i++) {
        int v;
        cin >> v;
        v += 1000000;
        l = max(l, last[v] + 1);
        left[i] = l;
        len[i] = i - l + 1;
        last[v] = i;
    }
    for (int i = 2; i <= n; i++)
        lg[i] = lg[i / 2] + 1;
    vector<vector<int>> st(lg[n] + 1, vector<int>(n));
    st[0] = len;
    for (int k = 1; k <= lg[n]; k++)
        for (int i = 0; i + (1 << k) <= n; i++)
            st[k][i] = max(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
    while (m--) {
        int L, R;
        cin >> L >> R;
        int p = upper_bound(left.begin() + L, left.begin() + R + 1, L) - left.begin(), ans = p - L;
        if (p <= R) {
            int k = lg[R - p + 1];
            ans = max(ans, max(st[k][p], st[k][R - (1 << k) + 1]));
        }
        cout << ans << '\n';
    }
}