题目描述
我们称一组整数序列为好的 \(k\)-\(d\) 序列，是指我们最多可以向序列中插入 \(k\) 个数，使得排序后该序列成为公差为 \(d\) 的等差数列。
你得到了一个由 \(n\) 个整数构成的序列 \(a\)，你的任务是找到该序列的最长连续子段，使其是一个好的 \(k\)-\(d\) 序列。
分析
好题，套路题目。
一道类似的题目为：CF526F Pudding Monsters。
最后是同样的处理方式。
好了，步入正题。
首先特判 \(d=0\) 的情况。
好，对于 \(d\geq 1\) 的情况考虑转化。
注意到等差序列满足：
- 模 \(d\) 同余。
- 值两两不同。
我们先把 \(a\) 变为正数，然后全部除以 \(d\)，这肯定是正确的，你可以想一想。
那么我们就全部转化为了 \(d=1\) 的情况。
考虑符合条件的序列 \([l,r]\) 满足什么：
- \(\max_{i\in[l,r]}a_i-\min_{i\in[l,r]}a_i-1-(r-l+1-2)\leq k\)。
- \([l,r]\) 内没有元素重复。
先考虑没有重复的情况：直接记录每个值之前出现最晚的位置。
考虑枚举 \(r\)，使得最左的 \(l\) 满足条件，且 \(l\in[x+1,r]\)，其中 \(x\) 表示 \(a_r\) 上次出现的位置。
那么我们只需要使：\(\max(l,r)-min(l,r)+l\leq k+r\) 即可。
那么我们如何维护这种东西呢？
注意 \(\max,\min\) 用单调栈是好维护的。
怎么维护呢？
考虑维护单调栈，栈中的每个点代表一段区间，它们的 \(\max\) 是这个栈中的元素，每次弹出时修改即可。
操作是区间加减，查询区间最左侧小于等于某个数的位置。
代码
时间复杂度 \(\mathcal{O}(n\log n)\)。
#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <unordered_map>
#define int long long
#define N 200005
using namespace std;
struct tree{int minval,pos;
}tr[N << 2];
int lz[N << 2];
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
void pushup(int x) {if (tr[ls(x)].minval < tr[rs(x)].minval) tr[x].pos = tr[ls(x)].pos;else if (tr[ls(x)].minval > tr[rs(x)].minval) tr[x].pos = tr[rs(x)].pos;else tr[x].pos = min(tr[ls(x)].pos,tr[rs(x)].pos);tr[x].minval = min(tr[ls(x)].minval,tr[rs(x)].minval);
}
void pushdown(int x) {tr[ls(x)].minval += lz[x],tr[rs(x)].minval += lz[x];lz[ls(x)] += lz[x],lz[rs(x)] += lz[x];lz[x] = 0;
}
void build(int x,int l,int r) {lz[x] = 0;if (l == r) return tr[x].minval = tr[x].pos = l,void();int mid = l + r >> 1;build(ls(x),l,mid),build(rs(x),mid + 1,r);pushup(x);
}
void update(int x,int l,int r,int L,int R,int val) {if (l > R || r < L) return;if (L <= l && r <= R) {tr[x].minval += val;lz[x] += val;return;}if (lz[x]) pushdown(x);int mid = l + r >> 1;update(ls(x),l,mid,L,R,val),update(rs(x),mid + 1,r,L,R,val);pushup(x);
}
int query(int x,int l,int r,int L,int R,int val) {if (l > R || r < L) return -1;if (tr[x].minval > val) return -1;if (l == r) return l;if (lz[x]) pushdown(x);int mid = l + r >> 1;if (L <= mid) {int res = query(ls(x),l,mid,L,R,val);if (res != -1) return res;}if (R > mid) return query(rs(x),mid + 1,r,L,R,val);return -1;
}
int n,a[N],k,d,b[N];
signed main(){cin >> n >> k >> d;for (int i = 1;i <= n;i ++) scanf("%lld",&a[i]);if (d == 0) {int pre = 1;int ansl = 1,ansr = 1;for (int i = 1;i <= n;i ++) {for (;a[i] == a[pre];i ++);if (ansr - ansl + 1 < i - pre) ansl = pre,ansr = i - 1;pre = i;i --;}if (a[n] == a[pre] && n - pre + 1 > ansr - ansl + 1) ansl = pre,ansr = n;cout << ansl << ' ' << ansr << '\n';return 0;}int best_len = 0, best_l = 0;for (int i = 1;i <= n;) {int j = i;int rem = ((a[i] % d) + d) % d;while (j <= n && ((a[j] % d + d) % d) == rem) j ++;int m = j - i;for (int p = 1;p <= m;p ++) {b[p] = (a[i + p - 1] - rem) / d;if (b[p] * d + rem != a[i + p - 1]) {if (a[i + p - 1] < 0) b[p]--;else b[p] ++;}}build(1,1,m);vector<pair<int,int>> max_stk, min_stk;unordered_map<int,int> last_pos;int T = 0;for (int r = 1;r <= m;r ++) {if (last_pos.count(b[r])) T = max(T, last_pos[b[r]]);last_pos[b[r]] = r;while (!max_stk.empty() && max_stk.back().second <= b[r]) {int idx = max_stk.back().first,val = max_stk.back().second;max_stk.pop_back();int prev_idx = max_stk.empty() ? 0 : max_stk.back().first;update(1,1,m,prev_idx + 1,idx,b[r] - val);}max_stk.emplace_back(r, b[r]);while (!min_stk.empty() && min_stk.back().second >= b[r]) {int idx = min_stk.back().first,val = min_stk.back().second;min_stk.pop_back();int prev_idx = min_stk.empty() ? 0 : min_stk.back().first;update(1,1,m,prev_idx + 1,idx,val - b[r]);}min_stk.emplace_back(r, b[r]);int L = query(1,1,m,T + 1,r,k + r);if (L != -1) {int cur_len = r - L + 1;if (cur_len > best_len) best_len = cur_len,best_l = i + L - 1;else if (cur_len == best_len && (i + L - 1) < best_l) best_l = i + L - 1;}}i = j;}cout << best_l << " " << best_l + best_len - 1 << endl;return 0;
}
/*
17 4 0
1 1 4 5 1 4 4 4 2 2 4 4 2 2 2 2 26 1 2
4 3 2 8 6 2*/