题意
给定 $n, m, k$ 和一个长度为 $n$ 的数组 $a$，满足 $1 \leq a_i \leq m$。
处理 $q$ 个询问，每次询问在 $\left[l, r\right]$ 中，至少删除几个数，能使得删完后的数组里，任意两个相邻的数的绝对值之差都不超过 $k$。
$1 \leq n \leq 10^5, 1 \leq q \leq 500$
题解
考虑对于每个询问暴力跑 DP，$f_i$ 表示以第 $i$ 个数结尾，最多能保留几个。离散化后用线段树维护可以达到 $O \left(qn \log n\right)$ 的复杂度。
但是我们有一个性质：对于一个值为 $a_i$ 的数，在最优解中，接在其后面的数只有两种可能，离 $i$ 最近的在 $\left[a_i - k, a_i\right]$ 内的数和离 $i$ 最近的在 $\left[a_i, a_i + k\right]$ 内的数。可以用 std::set 或者 线段树 平衡树 预处理。
对于每个询问，根据上述性质跑 DP 即可达到 $O\left(n \log n + nq\right)$ 的复杂度。
代码
/* C++17 is required!
* By Koicy (https://koicy.ly)
* Email n@rbtr.ee
* 我还期待着名为奇迹的魔法，哪怕会凋零会消散只会是一场浮华，我笑纳！
__ __ __ _
_____/ /_ / /_________ ___ / /______ (_)______ __
/ ___/ __ \/ __/ ___/ _ \/ _ \ ______ / //_/ __ \/ / ___/ / / /
/ / / /_/ / /_/ / / __/ __/ /_____/ / ,< / /_/ / / /__/ /_/ /
/_/ /_.___/\__/_/ \___/\___/ /_/|_|\____/_/\___/\__, /
SIGN /___*/
#define __NO_MAIN__ false
#define __ENABLE_RBLIB__ true
constexpr bool _MTS = true, SPC_MTS = false;
constexpr char EFILE[] = "";
#include <bits/stdc++.h>
#define FULL(arg) arg.begin(), arg.end()
// :/
using namespace std;
using tp = long long int;
using vetp = basic_string<tp>;
[[maybe_unused]] constexpr tp ZERO = 0, ONE = 1, INF = -1ull >> 2;
signed STRUGGLING(unsigned long long int);
void MIST();
#if !__NO_MAIN__
int main(int argc, char* argv[]) {
unsigned long long int t = 0, _t = 1;
MIST();
if (_MTS && !SPC_MTS) cin >> _t;
while (t < _t || SPC_MTS) {
if (STRUGGLING(++t) != 0) return 0;
}
return 0;
}
#endif
#ifdef XCODE
#define bg(...){cout<<"["<<__LINE__<<'@'<<++_LT[__LINE__]<<':';BG(__VA_ARGS__);}
size_t _LT[21777]; template<typename _Type>void BG(const _Type&_cur){cout<<' '<<
_cur << ']' << " <<:" << endl; } template<typename _Type,typename... _Other>void
BG(const _Type& _cur, const _Other& ..._other) {cout<< ' '<<_cur;BG(_other...);}
#else
#define bg(...)
#define dputs(...)
#endif
// :/
// :/
signed STRUGGLING([[maybe_unused]] unsigned long long int TEST_NUMBER) {
tp n, m, k; cin >> n >> m >> k;
vetp a(n + 1, 0);
for (tp i = 1; i <= n; ++i) cin >> a[i];
vetp id(n + 1, 0); iota(1 + FULL(id), 1);
vetp prv(n + 1, 0);
vetp nxt(n + 1, 0);
stable_sort(FULL(id), [&](tp x, tp y) { return a[x] < a[y]; });
[&]() {
tp p = n;
set<tp> s;
for (tp i = n; i >= 1; --i) {
s.insert(id[i]);
while (a[id[p]] - a[id[i]] > k) s.erase(id[p--]);
if (auto it = s.upper_bound(id[i]); it != s.end()) prv[id[i]] = *it;
}
}();
[&]() {
tp p = 1;
set<tp> s;
for (tp i = 1; i <= n; ++i) {
s.insert(id[i]);
while (a[id[i]] - a[id[p]] > k) s.erase(id[p++]);
if (auto it = s.upper_bound(id[i]); it != s.end()) nxt[id[i]] = *it;
}
}();
tp q; cin >> q;
while (q--) {
tp l, r; cin >> l >> r;
vetp f(n + 1, 1);
for (tp i = l; i <= r; ++i) {
for (auto& t : { prv[i], nxt[i] }) {
if (l <= t && t <= r) f[t] = max(f[t], f[i] + 1);
}
}
cout << r - l + 1 - *max_element(FULL(f)) << '\n';
}
return 0;
}
void MIST() {
cin.tie(nullptr)->sync_with_stdio(false);
}
// :\ */