[CF407E] k-d-sequence

复健不会写代码。

首先找充要条件，如一个子串 \(a_l,a_{l+1}...a_r\) 合法，则首先这些数互不重复，其次这些数对 \(d\) 取模相同，最重要的是

左边表示最终形成的等差数列中的数的个数，\(r - l\) 表示已经存在的数，那么剩下的数就需要填充。

感觉不难维护，那么考虑扫描线 + 线段树的套路。先从大到小枚举左端点，考虑右端点满足何性质。把上式中和 \(r\) 有关的分离出来，等价于

这启发我们在线段树上维护左边的这坨东西，下面称之为答案。\(-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);
}