[CF407E] k-d-sequence
复健不会写代码。
首先找充要条件，如一个子串 \(a_l,a_{l+1}...a_r\) 合法，则首先这些数互不重复，其次这些数对 \(d\) 取模相同，最重要的是
\[\dfrac{\max{a} - \min{a}}{d} - (r - l) \le k
\]
左边表示最终形成的等差数列中的数的个数，\(r - l\) 表示已经存在的数，那么剩下的数就需要填充。
感觉不难维护，那么考虑扫描线 + 线段树的套路。先从大到小枚举左端点，考虑右端点满足何性质。把上式中和 \(r\) 有关的分离出来，等价于
\[\dfrac{\max{a} - \min{a}}{d} - r \le k - l
\]
这启发我们在线段树上维护左边的这坨东西，下面称之为答案。\(-r\) 这一部分可以直接在建树的时候体现出来，注意到 \(\max a - \min a\) 必然是 \(d\) 的倍数，那么分式部分就可以转化为 \(\lfloor \frac{\max a}{d} \rfloor - \lfloor \frac{\min a}{d} \rfloor\)。考虑分开做 \(\max\) 和 \(\min\)，发现这俩杂糅在一起很难处理答案，那么继续拆拆拆，分别再维护不算 \(\max\) 和不算 \(\min\) 的答案，每次就只用考虑一者的贡献了。
现在还需要做区间取 \(\max\) 的操作，注意到优良性质：线段树中的 \(\max\) 单调递增。所以可以直接二分，但是我的做法是线段树上二分，常数可能会大一些。因为我们上面维护了那么多东西所以可以不用考虑 \(\min\) 的影响，直接打乱重来即可。
时间复杂度是优秀的 \(O(n \log n)\)，空间是 \(O(n)\)。常数比我的代码还大。
要注意，这题值域可以取到负数，因此需要整体平移。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
namespace IO {
#define isdigit(x) (x >= '0' && x <= '9')
template<typename T>
inline void read(T &x) {
x = 0; char ch = getchar(); int f = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
if(f) x = -x;
}
template<typename T, typename... Rest>
inline void read(T &x, Rest&... rest) {
read(x), read(rest...);
}
template<typename T>
inline void write(T x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
#undef isdigit
}
using namespace IO;
constexpr int N = 2e5 + 10;
const LL inf = 9223372036854775807;
int n, k;
LL a[N], d;
map<LL, int> vis;
struct SegmentTree {
#define lc (k << 1)
#define rc (k << 1 | 1)
#define mid ((l + r) / 2)
struct node {
LL mx1, mx2, mn1, mn2;
LL valx, valn, val;
LL tagx, tagn;
}tr[N << 2];
void update(int k) {
const node &l = tr[lc], &r = tr[rc];
tr[k] = (node){max(l.mx1, r.mx1), min(l.mx2, r.mx2), max(l.mn1, r.mx1), min(l.mn2, r.mn2),
min(l.valx, r.valx), min(l.valn, r.valn), min(l.val, r.val), -inf, inf};
}
void pushdown(int k, int l, int r) {
if(tr[k].tagx > -inf) {
const LL v = tr[k].tagx; tr[k].tagx = -inf;
tr[lc].val = v / d + tr[lc].valn, tr[rc].val = v / d + tr[rc].valn;
tr[lc].valx = v / d - mid, tr[rc].valx = v / d - r;
tr[lc].mx1 = tr[lc].mx2 = tr[rc].mx1 = tr[rc].mx2 = v;
tr[lc].tagx = max(tr[lc].tagx, v), tr[rc].tagx = max(tr[rc].tagx, v);
}
if(tr[k].tagn < inf) {
const LL v = tr[k].tagn; tr[k].tagn = inf;
tr[lc].val = -v / d + tr[lc].valx, tr[rc].val = -v / d + tr[rc].valx;
tr[lc].valn = -v / d - mid, tr[rc].valn = -v / d - r;
tr[lc].mn1 = tr[lc].mn2 = tr[rc].mn1 = tr[rc].mn2 = v;
tr[lc].tagn = min(tr[lc].tagn, v), tr[rc].tagn = min(tr[rc].tagn, v);
}
}
void build(int k, int l, int r) {
if(l == r) {
tr[k] = (node){a[l], a[l], a[l], a[l], a[l] / d - l, -a[l] / d - l, -l, -inf, inf};
return ;
}
build(lc, l, mid), build(rc, mid + 1, r);
update(k);
}
void modifyx(int k, int l, int r, int L, int R, LL v) {
if(r < L || R < l || tr[k].mx2 >= v)
return ;
if(L <= l && r <= R && tr[k].mx1 <= v) {
tr[k].mx1 = tr[k].mx2 = v, tr[k].val = v / d + tr[k].valn;
tr[k].valx = v / d - r, tr[k].tagx = max(tr[k].tagx, v);
return ;
}
pushdown(k, l, r);
modifyx(lc, l, mid, L, R, v);
modifyx(rc, mid + 1, r, L, R, v);
update(k);
}
void modifyn(int k, int l, int r, int L, int R, LL v) {
if(r < L || R < l || tr[k].mn1 <= v)
return ;
if(L <= l && r <= R && tr[k].mn2 >= v) {
tr[k].mn1 = tr[k].mn2 = v, tr[k].val = -v / d + tr[k].valx;
tr[k].valn = -v / d - r, tr[k].tagn = min(tr[k].tagn, v);
return ;
}
pushdown(k, l, r);
modifyn(lc, l, mid, L, R, v);
modifyn(rc, mid + 1, r, L, R, v);
update(k);
}
int query(int k, int l, int r, int L, int R, LL v) {
if(r < L || R < l || tr[k].val > v)
return 0;
if(l == r) return l;
pushdown(k, l, r);
int res = query(rc, mid + 1, r, L, R, v);
if(res) return res;
return query(lc, l, mid, L, R, v);
}
#undef lc
#undef rc
#undef mid
}s;
int main() {
read(n, k, d);
for(int i = 1; i <= n; ++i)
read(a[i]), a[i] += 1e9;
if(d == 0) {
int ansl = 1, ansr = 0;
for(int i = 1, l = 1; i <= n; ++i) {
if(a[i] != a[i - 1]) l = i;
if(i - l > ansr - ansl)
ansr = i, ansl = l;
}
printf("%d %d\n",ansl,ansr);
return 0;
}
int ansl = 1, ansr = 0;
s.build(1, 1, n);
for(int l = n, cur = n; l >= 1; --l) {
if(l < n && a[l] % d != a[l + 1] % d)
cur = l, vis.clear();
if(vis[a[l]]) {
for(int j = vis[a[l]] + 1; j <= cur; ++j)
vis[a[j]] = 0;
cur = vis[a[l]] - 1;
}
vis[a[l]] = l;
s.modifyx(1, 1, n, l + 1, cur, a[l]);
s.modifyn(1, 1, n, l + 1, cur, a[l]);
int r = s.query(1, 1, n, l, cur, k - l);
if(r - l >= ansr - ansl)
ansr = r, ansl = l;
}
printf("%d %d\n",ansl,ansr);
}