思路

• 一开始想了好久，找了好几篇题解，看懂了后感觉妙不可言。决定记录一下这一题。
• 首先要解决这题，有两步，第一步预处理，第二步RMQ查询。第一步预处理有两种方法，一种是双指针（滑动窗口），一种是dp的思想;至于第二步RMQ可以用线段树和ST表来做，我这里只用了ST表，感觉重点是预处理的部分，因为预处理的处理方式有点难想。
• 首先是第一步预处理，核心就是计算两个东西：一个是以$a[i]$为结尾的最长“完美序列”的长度$len[i]$，另一个是这个“完美序列”的开头的下标$indx[i]$。
• 下面给出两个方法来预处理这两个数组
• 双指针的做法，细节看注释

    for (int l = 1, r = 1; r <= n; ++r) {
        int i = a[r] + dif;// dif = 1e6, 用来处理负数
        ++cnt[i]; // 计数器自增
        while (l < r && cnt[i] > 1) --cnt[a[l++] + dif]; // 找到下标r的最长完美序列的开头
        len[r] = r - l + 1, indx[r] = l; // 计算两个数组
    }

• dp的做法，细节看注释

    for (int i = 1; i <= n; ++i) {
        int x = a[i] + dif; // dif = 1e6, 用来处理负数
        indx[i] = max(indx[i - 1], last[x] + 1); // last数组记录的是x最近出现的下标
        len[i] = i - indx[i] + 1; // 计算len
        last[x] = i; // 更新x最近出现的下标
    }

• 第二步，即接下来说着这两个数组有什么用：当询问区间$[L, R]$的“完美序列”长度时，对于一个下标 $i \ \ (L \le i \le R)$，若$indx[i]\ge L$，显然答案在这些$i$中的最大值中，若$indx[i] < L$，则答案就是$indx[i]$中最接近$L$的下标$i - L + 1$。答案就是两者的最大值，前者就是RMQ，后者可以用二分找到最接近$L$的下标$i$，因为indx数组是递增的
• ac 代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cctype>
inline long long IO() {
    long long x = 0;
    bool f = false;
    char c = getchar();
    while (!isdigit(c)) {
        if (c == '-') f = true;
        c = getchar();
    }
    while (isdigit(c)) {
        x = (x << 1) + (x << 3) + (c - '0');
        c = getchar();
    }
    return f ? -x : x;
}
using namespace std;

const int N = 2e6 + 5, M = 2e5 + 5, dif = 1e6;
int lg[M] = {-1}, st[M][30], n, m, len[M], a[M], cnt[N], indx[M];
// st表预处理, 注意下标从1开始到n结束
void init(int *a, int n) {
    for (int i = 1; i <= n; ++i) lg[i] = lg[i >> 1] + 1, st[i][0] = a[i];
    for (int j = 1; j <= lg[n]; ++j) {
        int k = 1 << (j - 1);
        for (int i = 1; i + k - 1 <= n; ++i) {
            st[i][j] = max(st[i][j - 1], st[i + k][j - 1]);
        }
    }
}
// 询问
int get(int l, int r) {
    int x = lg[r - l + 1];
    return max(st[l][x], st[r - (1 << x) + 1][x]);
}

int main() {
    n = IO(), m = IO();
    for (int i = 1; i <= n; ++i) a[i] = IO();
    for (int l = 1, r = 1; r <= n; ++r) {
        int i = a[r] + dif;
        ++cnt[i];
        while (l < r && cnt[i] > 1) --cnt[a[l++] + dif];
        len[r] = r - l + 1, indx[r] = l;
    }
    init(len, n);
    while (m--) {
        int a = IO() + 1, b = IO() + 1;
        int l = a, r = b, res = a;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (indx[mid] < a) res = mid, l = mid + 1;
            else r = mid - 1;
        }
        int ans = res - a + 1;
        if (res < b) ans = max(ans, get(res + 1, b));
        printf("%d\n", ans);
    }
    return 0;
}

• 总结：有时候一个问题看起来像是RMQ问题，但是却不是裸的RMQ，可以考虑预处理一些东西来变成一个RMQ问题