传送门：P16796 [蓝桥杯 2026 国 B] 灯带修补
更佳的阅读体验：洛谷 P16796 题解

简要题意：给你一个环，你需要求出环上最长的连续子段，使得该字段中相邻元素之差的绝对值 $> k$ 的位置数量 $\le m$。$n \le 2 \times 10^5$。

看到环，我们应该就有一个直觉是需要把整个序列在数组末尾再复制一次，这样环上问题就被转化成线性的序列问题了。

我们发现，最后的答案其实只和相邻元素之差的绝对值有关，而与 $a_i$ 本身的值无关。此时，如果我们将 $|a_i - a_{i + 1}| > k$ 视作 $1$，否则为 $0$，那我们就可以得到一个新的序列，即 $d_i = \left [|a_i - a_{i + 1}| > k \right ]$，其中 $[P]$ 为条件表达式，命题 $P$ 为真时值为 $1$，否则为 $0$。

这时，我们对序列 $d$ 再做一次前缀和，我们就可以很简单地求出来每个区间有多少个位置符合条件了。那反过来想，其实只需要遍历一次序列 $d$，查找最后一个不超过 $d_i + m$ 的位置即可。

时间复杂度 $O(n \log n)$。

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
using ll = long long;

const int N = 4e5 + 10;
int n, m, ans;
ll k, a[N], d[N];

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    copy(a + 1, a + n + 1, a + n + 1);
    for (int i = 1; i < (n << 1); ++i) d[i] = d[i - 1] + (abs(a[i] - a[i + 1]) > k);
    for (int i = 1; i <= n; ++i)
        ans = max(ans, min(n, int(upper_bound(d + 1, d + (n << 1) + 1, d[i] + m) - d - i)));
    cout << ans << '\n';
    return 0;
}