题意

给定序列 $a _ 1, a _ 2, \cdots, a _ n \ (n \le 10 ^ 6)$ 和两个正整数 $A, B \ (A \le B)$，求一个最长的子区间 $a _ l, a _ {l + 1}, \cdots a _ r$，满足

$$A \le \max \{ a _ l, a _ {l + 1}, \cdots a _ r \} - \min \{ a _ l, a _ {l + 1}, \cdots a _ r \} \le B$$

输出最长的区间长度，若不存在则输出 $0$。

样例

样例输入 #1

5 0 0
1 1 1 1 1

样例输出 #1

5

样例输入 #2

5 0 3
1 2 3 4 5

样例输出 #2

4

大致的思路是，先预处理出 ST 表。然后有一个性质：对于已知的 $l$，$\max \{ a _ l, a _ {l + 1}, \cdots a _ r \} - \min \{ a _ l, a _ {l + 1,} \cdots, a _ r \}$ 随 $r$ 的增大而不减，所以用尺取法，对于一个 $l$，找到最大的 $r$ 使得 $\max \{ a _ l, a _ {l + 1}, \cdots a _ r \} - \min \{ a _ l, a _ {l + 1,} \cdots, a _ r \} \le B$，用 $r - l + 1$ 更新答案并 $l \gets l + 1$ 进行下一次尺取。

但是坑爹 OJ 不提供分数和测试点，只告诉我 WA 了，也许是有小问题。求调。

#include <iostream>
#include <cmath>

int a[1000005], st[1000005][25][2];

int query(int l, int r)
{
    int k = log2(r - l + 1);
    return std::max(st[l][k][0], st[r - (1 << k) + 1][k][0]) - std::min(st[l][k][1], st[r - (1 << k) + 1][k][1]);
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int n, A, B, maxx = 0, len = 0;

    std::cin >> n >> A >> B;
    maxx = A;
    for (int i = 1; i <= n; i++)
        std::cin >> a[i];

    for (int i = 1; i <= n; i++)
        st[i][0][0] = st[i][0][1] = a[i];
    for (int len = 1; 1 << len <= n; len++)
        for (int i = 1; i + (1 << len) - 1 <= n; i++)
        {
            st[i][len][0] = std::max(st[i][len - 1][0], st[i + (1 << (len - 1))][len - 1][0]);
            st[i][len][1] = std::min(st[i][len - 1][1], st[i + (1 << (len - 1))][len - 1][1]);
        }

    maxx = A;
    for (int i = 1, j = 1; i <= n && j <= n; i++)
    {
        while (query(i, j + 1) <= B && j < n)
            j++;
        if (query(i, j) >= maxx && j - i + 1 > len)
        {
            maxx = query(i, j);
            len = j - i + 1;
        }
    }

    std::cout << len << "\n";

    return 0;
}