题目描述

思路

1. 询问的是区间[L, R]，完美序列的开始下标 >= L
2. 二分查找序列中满足开始下标大于L的第一个位置x
3. ST算法求解[x, R]的最大长度 y
4. x - L 和 y 的最大值为结果

代码

#include <cstdio>
#define max(a,b) ((a) > (b) ? (a) : (b))
const int MAX = 1000000;
int arr[200005], last[2000006], st[200005];
int f[200005][21], log[200005], rec[200005];
int res;
inline int read() {
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * f;
}
int n, m;
// 找出可以应用st算法的第一个值
int find(int l, int r) {
    if (st[l] >= l) return l;
    if (st[r] < l) return r + 1;
    int ans = 0, L = l, R = r, mid;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (st[mid] >= L) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    return ans;
}

int query(int l, int r) {
    int x = log[r - l + 1];
    return max(f[l][x], f[r - (1 << x) + 1][x]);
}

int main() {
    n = read(), m = read();
    log[0] = -1;
    for (int i = 1; i <= n; ++i) {
        arr[i] = read();
        log[i] = log[i >> 1] + 1;
        st[i] = max(st[i - 1], last[arr[i] + MAX] + 1);
        rec[i] = i - st[i] + 1;
        f[i][0] = rec[i];
        last[arr[i] + MAX] = i;
    }
    
    for (int i = 1; i <= 20; ++i) {
        for (int j = 1; j + (1 << i) - 1 <= n; ++j) {
            f[j][i] = max(f[j][i - 1], f[j + (1 << (i - 1))][i - 1]);
        }
    }
    
    for (int i = 1, a, b, c, d, e; i <= m; ++i) {
        a = read(), b = read();
        res = 0, a++, b++;
        c = find(a, b);
        if (c > a) res = c - a;
        if (c <= b) res = max(res, query(c, b));
        printf("%d\n", res);
    }
    return 0;
}