487B

Description

Given a sequence of numbers of length $n$. ($1 \leq n \leq 10^5$) It require us to split the sequence into several substrip, and the difference between the maximum value and minimum value in each strip is no greater than $l$, and the length of each substrip must be greater than $s$. Output the minimal number of strip it could be divided into.

Tutorial

Use dynamic programming to solve the problem. Let $f[i]$ denote the minimal number of pieces that the first $i$ numbers can be split into. $g[i]$ denote the least possible left boarder of substrip whose right border is $i$ which satisfies the condition. Then $f[i] = min(f[k]) + 1$, where $g[i] ≤ k ≤ i - l$.

One possible way to calculate $g[i]$ is to use monotonic queue which can be done in $O(n)$. But it is hard to implement, since we need to maintain 2 monotonic queues to for the maximal and minimal value, especially when it comes to the pop operation.

Here we have a alternative way to do this, multiset. Multiset is a STL container which have the same function of STL set, however, it can store multiple items of the same value. We can insert and erase a element by $O(logN)$, which is slower than the push and pop of monotonic queue which is $O(1)$. Quest any element in multiset (e.g. maximum, minimum) in $O(1)$. (I cannot believe that) It can be used as follows.

multiset<E> m;
m.insert(a);    //insert a into the multiset
m.erase(m.lower_bound(a));  //delete a from the multiset
*m.begin(); //the minimum element
*(--m.end());   //the maximum element

With so easy to access the maximum and minimum, we can finish the task of calculating $g[i]$ with a process of two pointers, which is to push the right boarder by 1 and to push the left boarder until it satisfies the condition.

We can also use either monotonic queue or multiset to calculate $f[i]$, because its also a task of finding the minimal between the two pointers.

Solution

#include <cstdio>
#include <cmath>
#include <set>
using namespace std;

#define MAX_N 100005
#define D(x) 
#define INF 0x3f3f3f3f

int n, s, max_diff;
int seq[MAX_N];
int f[MAX_N], g[MAX_N];

void input()
{
    scanf("%d%d%d", &n, &max_diff, &s);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &seq[i]);
    }
}

int work()
{
    multiset<int> multi_set;
    int left = 0;
    for (int i = 0; i < n; i++)
    {
        multi_set.insert(seq[i]);
        while (!multi_set.empty())
        {
            int min_val = *multi_set.begin();
            int max_val = *(--multi_set.end());
            D(printf("  min=%d\n", min_val));
            D(printf("  max=%d\n", max_val));
            if (max_val - min_val <= max_diff)
            {
                break;
            }
            D(printf("  left=%d\n", left));
            multi_set.erase(multi_set.lower_bound(seq[left]));
            left++;
        }
        g[i] = left;
        D(printf("g[%d]=%d\n", i, g[i]));
    }

    multi_set.clear();
    f[0] = 0;
    for (int i = 0; i < s - 1; i++)
    {
        f[i + 1] = INF;
    }
    left = -1;
    for (int i = s - 1; i < n; i++)
    {
        D(printf("f[i]=%d\n", f[i]));
        D(printf("%d\n", i));
        D(printf("  in:%d\n", i-s));
        multi_set.insert(f[i - s + 1]);
        while (left < g[i] - 1 && left <= i - s)
        {
        D(printf("  out:%d\n", left));
            multi_set.erase(multi_set.lower_bound(f[left + 1]));
            left++;
        }
        if (multi_set.empty())
        {
            f[i + 1] = INF;
            continue;
        }
        f[i + 1] = *multi_set.begin() + 1;
    }
    if (f[n] >= INF)
    {
        return -1;
    }
    return f[n];
}

int main()
{
    input();
    printf("%d\n", work());
    return 0;
}