给你一个长为 \(n\) 的序列，求最长的子区间使得它加入至多 \(k\) 个数后，重排后是公差为 \(d\) 的等差数列。
\(n, k \le 2 \times 10^5\)，\(0 \le d \le 10^9\)。
公差是 \(d\) 的等差数列模 \(p\) 的值应该相等，所以把序列按极长模 \(p\) 同余的连续段分组。
对于同一组，我们将每个数都除以 \(d\)，然后就转化成了求公差为 \(1\) 的等差数列。
如果一段区间 \([l, r]\) 满足要求，这就相当于要求 \([l, r]\) 中的数是值域上连续的一段且互不相等。然后套上 Good Subsegments 的判定方法就做完了（也就是判定 \(\max - \min - (r - l) \le k\)）。
时间复杂度 \(O(n \log n)\)。
constexpr int MAXN = 2e5 + 9, DLT = 1e9 + 1;
int n, k, d, a[MAXN], lst[MAXN], ans = 0, ansl, ansr;
vector<int> stk[2];
map<int, int> vis;
struct Node {
ll mn, tag;
} sgt[MAXN << 2];
void Push_Up(int p) {
sgt[p].mn = min(sgt[p << 1].mn, sgt[p << 1 | 1].mn);
return;
}
void Push_Tag(int p, ll k) {
sgt[p].mn += k, sgt[p].tag += k;
return;
}
void Push_Down(int p) {
if (sgt[p].tag) {
Push_Tag(p << 1, sgt[p].tag);
Push_Tag(p << 1 | 1, sgt[p].tag);
sgt[p].tag = 0;
}
return;
}
void Build(int L = 1, int R = n, int p = 1) {
if (L == R) return sgt[p].mn = L - k, void();
int Mid = L + R >> 1;
Build(L, Mid, p << 1), Build(Mid + 1, R, p << 1 | 1);
Push_Up(p); return;
}
void Update(int l, int r, ll k, int L = 1, int R = n, int p = 1) {
if (l <= L && R <= r) return Push_Tag(p, k);
Push_Down(p); int Mid = L + R >> 1;
if (l <= Mid) Update(l, r, k, L, Mid, p << 1);
if (Mid < r) Update(l, r, k, Mid + 1, R, p << 1 | 1);
Push_Up(p); return;
}
int Query(int l, int r, int L = 1, int R = n, int p = 1) {
if (l <= L && R <= r) {
if (sgt[p].mn > 0) return -1;
while (L < R) {
Push_Down(p); int Mid = L + R >> 1;
if (sgt[p << 1].mn <= 0) R = Mid, p <<= 1;
else L = Mid + 1, p = (p << 1 | 1);
}
return L;
}
Push_Down(p); int Mid = L + R >> 1;
if (r <= Mid) return Query(l, r, L, Mid, p << 1);
if (Mid < l) return Query(l, r, Mid + 1, R, p << 1 | 1);
int ret = Query(l, r, L, Mid, p << 1);
if (~ret) return ret;
return Query(l, r, Mid + 1, R, p << 1 | 1);
}
int qry(int pos, int L = 1, int R = n, int p = 1) {
if (L == R) return sgt[p].mn;
Push_Down(p); int Mid = L + R >> 1;
if (pos <= Mid) return qry(pos, L, Mid, p << 1);
else return qry(pos, Mid + 1, R, p << 1 | 1);
}
void slv() {
n = Read<int>(), k = Read<int>(), d = Read<int>();
for (int i = 1; i <= n; i ++) a[i] = Read<int>() + DLT, vis[a[i]] = 0;
for (int i = 1; i <= n; i ++) lst[i] = vis[a[i]], vis[a[i]] = i;
if (d == 0) {
for (int l = 1, r; l <= n; l = r + 1) {
r = l;
while (r + 1 <= n && a[r + 1] == a[l]) r ++;
if (r - l + 1 > ans) ans = r - l + 1, ansl = l, ansr = r;
}
Write(ansl, ' '), Write(ansr, '\n');
return;
}
Build();
for (int l = 1, r; l <= n; l = r + 1) {
r = l; int mx = l;
while (r + 1 <= n && a[r + 1] % d == a[r] % d) r ++;
stk[0].clear(), stk[0].emplace_back(l - 1);
stk[1].clear(), stk[1].emplace_back(l - 1);
Update(l, r, - (l - 1));
for (int i = l; i <= r; i ++) {
cmax(mx, lst[i] + 1), a[i] /= d;
while (stk[0].size() > 1 && a[stk[0].back()] <= a[i])
Update(stk[0][stk[0].size() - 2] + 1, stk[0].back(), - a[stk[0].back()]), stk[0].pop_back();
Update(stk[0].back() + 1, i, a[i]), stk[0].emplace_back(i);
while (stk[1].size() > 1 && a[stk[1].back()] >= a[i])
Update(stk[1][stk[1].size() - 2] + 1, stk[1].back(), a[stk[1].back()]), stk[1].pop_back();
Update(stk[1].back() + 1, i, - a[i]), stk[1].emplace_back(i);
Update(l, r, -1);
int j = Query(mx, i);
if (~j && i - j + 1 > ans) ans = i - j + 1, ansl = j, ansr = i;
}
}
Write(ansl, ' '), Write(ansr, '\n');
return;
}
``