题解：P14058 【MX-X21-T3】[IAMOI R5] 两个人的演唱会

先特判这个环本身极差就不超过 \(m\) 的情况（此时答案为 \(1\)）。

原问题在环上，不是很好解决，先考虑解决一个更简单的问题：

小 R 有一个长度为 \(n\) 的，由正整数组成的链 \(a_1,\dots,a_n\)，她要你将这个链切成若干段，使得所有段的段内极差都小于等于 \(m\)，求分成的最少段数。

这是一个经典的贪心问题。显然，在所有切法中，每次切出最长的极差不超过 \(m\) 的前缀一定不劣。使用双指针维护，动态维护左右指针中间部分的最大值和最小值即可。

现在问题被转化为，我们应该在何处将环断为链，才能得到最优答案。乍一看确实无从下手，因此想到考虑环上的一些“特殊”位置。

考察任意一个最小值位置 \(a_x\)，取出它所在的段，那么这一段的极差不超过 \(m\)，等价于段内任意一个 \(a_y\) 都满足 \(a_y\le a_x+m\)。符合要求的极长段是唯一的，也就是说，对于任意一种合法的切分方式，\(a_x\) 所在的段都一定包含于这个极长段之中。根据贪心的思想，切出这一极长段一定不劣。

切出这一段后，剩下的部分自然断成了一条链，使用前面提到的双指针即可求出答案。

时间复杂度 \(O(\sum n)\)。

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;const int N = 3e7 + 5;int T, n, m, a[N];int main() {ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);for(cin >> T; T; --T) {cin >> n >> m;rep(i, 0, n - 1) cin >> a[i];if(*max_element(a, a + n) - *min_element(a, a + n) <= m) {cout << 1 << endl;continue;}int argmin = min_element(a, a + n) - a;int pl = argmin, pr = argmin;auto pre = [&](int x) {return (x + n - 1) % n;};auto nxt = [&](int x) {return (x + 1) % n;};while(a[pre(pl)] - a[argmin] <= m) pl = pre(pl);while(a[nxt(pr)] - a[argmin] <= m) pr = nxt(pr);int ans = 1, p = nxt(pr), mx = a[p], mn = a[p];while(p != pl) {chkmax(mx, a[p]);chkmin(mn, a[p]);if(mx - mn > m) {++ans;mx = mn = a[p];}p = nxt(p);}cout << ans + 1 << endl;}return 0;
}