区间最长连续不重复子序列

· · 题解

题目链接

弱化版

给定一个长度为 N 的序列 A。

要找到一对下标 l, r，使得 A_l \sim A_r 这个子区间里所有数字都是独一无二的～
我们希望区间长度 r - l + 1 越大越好，然后把这个最大长度输出。
如果有多组解，就选 l 最小的那一个哦。

弱化版题解

这个简单版本有好几种可爱的解法呢！比如二分答案或者双指针，都能在 O(n\log n) 甚至 O(n) 的时间里解决。

二分答案法：
我们先猜一个可能的区间长度 len，然后花 O(n) 的时间检查这个长度是否合法。
由于合法的长度是单调的（如果某个长度可行，那么更短的长度一定也可行），所以可以安心地二分答案。总时间复杂度是 O(n \log n)。

双指针法：
维护两个指针 l 和 r，每次把 r 向右移动一格，同时把 l 向右调整到第一个让区间 [l, r] 内所有元素依然不重复的位置。
容易发现 l 指针只会向右走，不会回头，所以整个扫描过程是 O(n) 的，非常高效！

小提示：如果用弱化版的 O(n \log n) 二分做法，可以通过强化版中 48 分的数据；如果用 O(n) 的双指针，能通过 60 分的数据哟。

强化版

强化版在线做法（可以愉快地处理多次询问）

我们来定义两个辅助数组：

首先预处理一个 pre_i，它记录在位置 i 之前、上一个与 A_i 相同数字出现的位置。如果之前没出现过，就记作 0。这个数组可以轻松地用 O(n) 算出来。

对于每个起点 i，我们想找到最大的 x，使得区间 [i, x] 里所有位置的 pre 值的最大值都小于 i。这样就保证区间内每个数字都是第一次出现啦～
因为当 i 固定时，这个区间 pre 最大值是随着 x 增大而单调不减的，所以我们可以用二分查找来找到这个 x。然后令 f_i = x，g_i = x - i + 1。

要实现这个二分，我们需要能快速查询任意区间 [i, mid] 内 pre 的最大值。这可以用第一个线段树或者 ST 表来维护。

这里有一个重要性质：f 数组是单调不降的。
简单证明一下：假设存在 i < j 但 f_i > f_j。因为区间 [i, f_i] 没有重复数字，而 j 在 i 的右边，那么从 j 出发至少也能走到 f_i 呀，这就和 f_j 的定义矛盾啦。所以 f 一定是单调不降的。

现在来看每次询问 [L, R] 该怎么回答。答案可能来自以下两种情况：

  1. 起点 x 的“势力范围”超出了 R：我们找到第一个满足 L \le x \le R 且 f_x > R 的位置 x。那么对于这个起点，它在询问区间内能贡献的长度就是 R - x + 1。由于 f 单调，这个 x 可以用二分快速找到。
  2. 起点落在 [L, x-1] 里：这些起点的 f 值都不超过 R，所以它们能贡献的长度就是对应的 g 值。我们只需要查询 g 在区间 [L, x-1] 上的最大值就好啦。

对于情况二，我们需要第二个数据结构（线段树或 ST 表）来维护 g 数组的区间最大值。
最终答案就是 \max(R - x + 1, \max_{k=L}^{x-1} g_k)。

这样我们就能高效地处理每一个询问了！

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
#define low_bit(x) ((x)&-(x))
using namespace std;
using ll = long long;
const int N = 2e5 + 5, M = 1e5 + 5;

int n, q, a[N];
int f[N], g[N], pre[N], d[M]; // d用于记录每个值最后出现的位置
int t1[N << 2], t2[N << 2]; // t1维护g，t2维护pre的最大值

void push_up(int num, int zt){
    if(zt == 1) t1[num] = max(t1[num << 1], t1[num << 1 | 1]);
    if(zt == 2) t2[num] = max(t2[num << 1], t2[num << 1 | 1]);
}

void build(int num, int l, int r, int zt){
    if(l == r){
        if(zt == 1) t1[num] = g[l];
        if(zt == 2) t2[num] = pre[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(num << 1, l, mid, zt);
    build(num << 1 | 1, mid + 1, r, zt);
    push_up(num, zt);
}

int qry(int num, int l, int r, int L, int R, int zt){
    if(l > R || r < L) return 0;
    if(L <= l && r <= R){
        if(zt == 1) return t1[num];
        return t2[num];
    }
    int mid = (l + r) >> 1;
    return max(qry(num << 1, l, mid, L, R, zt),
               qry(num << 1 | 1, mid + 1, r, L, R, zt));
}

// 检查区间 [l, x] 的 pre 最大值是否 < l
bool check(int l, int x){
    return qry(1, 1, n, l, x, 2) < l;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    // 计算pre数组
    for(int i = 1; i <= n; i++){
        pre[i] = d[a[i]];
        d[a[i]] = i;
    }
    // 建立维护pre最大值的线段树
    build(1, 1, n, 2);
    // 计算f和g数组
    for(int i = n; i >= 1; i--){
        int l = i + 1, r = n, ans = i;
        while(l <= r){
            int mid = (l + r) >> 1;
            if(check(i, mid)) l = mid + 1, ans = mid;
            else r = mid - 1;
        }
        f[i] = ans;
        g[i] = ans - i + 1;
    }
    // 建立维护g最大值的线段树
    build(1, 1, n, 1);
    cin >> q;
    while(q--){
        int x, y; cin >> x >> y;
        // 二分查找分界点p：第一个满足 f[p] > y 的位置
        int l = x, r = y, p = y + 1;
        while(l <= r){
            int mid = (l + r) >> 1;
            if(f[mid] > y) r = mid - 1, p = mid;
            else l = mid + 1;
        }
        int ans = 0;
        // 情况1：左端点为p，贡献为 y - p + 1
        if(p != y + 1){
            ans = y - p + 1;
            if(p == x){ // 整个区间都属于情况1
                cout << ans << '\n';
                continue;
            }
        }
        // 情况2：左端点在 [x, p-1] 中，贡献为g的最大值
        cout << max(qry(1, 1, n, x, p - 1, 1), ans) << '\n';
    }
    return 0;
}