CF407E k-d-sequence

考虑扫描线，右指针不断向右移动，数据结构维护左指针是否合法。

如何判断一段区间是否合法？首先考虑 $d = 0$ 的情况，特判这种情况，只需要找到一段最大的值相同的段即可；否则，因为是公差为 $d$ 的等差数列，可以写作 $a _ 0 + i \times d$ ，那么一定是模 $d$ 意义下相等的的数，而 $i$ 各自不一样，所有的数 $\frac {w _ i - w _ 0} d = i$ 一定是一段区间的排列。按照套路则有 $max - min = r - l$ ，特别地，因为可以添加 $k$ 个数，则 $max - min \le r - l + k$ ，且其中不能有相同的数，考虑维护 $w _ i = max - min - r + l - k$ ，可以用单调栈维护一段后缀的最值，需要支持区间加减，查询最小的 $i$ 使得 $w _ i \le 0$ ，线段树即可。注意如果有相同的数，需要将前面的数删除，直接区间加 $inf$ 即可。

查看代码

#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
typedef long long LL;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 2e5 + 10, inf = 1e9;
int n, h, d, w[N];
struct Node
{
    int l, r;
    LL tag, mn;
} tr[N << 2];
void pushup (int x)
{
    tr[x].mn = min(tr[x << 1].mn, tr[x << 1 | 1].mn);
}
void add (int x, LL k)
{
    tr[x].mn += k, tr[x].tag += k;
}
void pushdown (int x)
{
    add(x << 1, tr[x].tag), add(x << 1 | 1, tr[x].tag);
    tr[x].tag = 0;
}
void build (int l = 1, int r = n, int x = 1)
{
    tr[x].l = l, tr[x].r = r;
    if (l == r)
        return tr[x].mn = l - h, void();
    int mid = l + r >> 1;
    build(l, mid, x << 1), build(mid + 1, r, x << 1 | 1);
    pushup(x);
}
void modify (int l, int r, LL k, int x = 1)
{
    if (l > r || tr[x].l > r || l > tr[x].r)
        return;
    if (tr[x].l >= l && tr[x].r <= r)
        return add(x, k);
    pushdown(x);
    modify(l, r, k, x << 1), modify(l, r, k, x << 1 | 1);
    pushup(x);
}
int query (int x = 1)
{
    if (tr[x].l == tr[x].r)
        return tr[x].l;
    pushdown(x);
    return query(tr[x << 1].mn <= 0 ? x << 1 : x << 1 | 1);
}
map <int, int> pre;
int top1, stk1[N], top2, stk2[N];
int main ()
{
    read(n), read(h), read(d);
    for (int i = 1; i <= n; i++)
        read(w[i]), w[i] += inf;
    if (!d)
    {
        int L = 1, R = 0;
        for (int l = 1, r = 1; l <= n; l = r + 1)
        {
            while (r < n && w[l] == w[r + 1])
                r++;
            r - l > R - L && (L = l, R = r);
        }
        write(L), putchar(' '), write(R);
        return 0;
    }
    build();
    int L = 1, R = 0;
    for (int i = 1, l = 1; i <= n; i++)
    {
        w[i] % d ^ w[i - 1] % d && (l = i);
        pre.count(w[i]) && (l = max(l, pre[w[i]] + 1));
        modify(1, l - 1, inf + n + h);
        pre[w[i]] = i;
        while (top1 && w[stk1[top1]] > w[i])
            modify(stk1[top1 - 1] + 1, stk1[top1], w[stk1[top1]] / d), top1--;
        modify(stk1[top1] + 1, i, -w[i] / d);
        stk1[++top1] = i;
        while (top2 && w[stk2[top2]] < w[i])
            modify(stk2[top2 - 1] + 1, stk2[top2], -w[stk2[top2]] / d), top2--;
        modify(stk2[top2] + 1, i, w[i] / d);
        stk2[++top2] = i;
        modify(1, n, -1);
        int t = query();
        i - t > R - L && (L = t, R = i);
    }
    write(L), putchar(' '), write(R);
    return 0;
}