VOJ - VMQUABEO

Source: VMQUABEO

Tags: Data Structures

Problem:

Cân nặng của Wolfris đã đến mức báo động, nên anh quyết định đi tập chạy để giảm cân. Khu vực Wolfris sống có một con đường dài, điểm đầu của con đường là điểm 1, điểm cuối con đường là điểm N. Các điểm cách đều nhau 1 đơn vị, điểm thứ i có độ cao H[i]. Wolfris muốn chọn ra một đoạn đường để tập chạy sao cho:

- Độ dài đoạn đường ít nhất là L.

- Chênh lệch giữa điểm cao nhất và thấp nhất trong đoạn đường không vượt quá D.

Hãy giúp Wolfris xác định có bao nhiêu đoạn đường thỏa mãn.

1 ≤ L < N ≤ 1e6.

0 ≤ D ≤ 1e4.

1 ≤ H[i] ≤ 1e4.

Ví dụ:

Input:

10 3 4

5 6 9 7 4 3 5 6 8 8

Output:

5

Explanation:

Các đoạn đường phù hợp là

(1, 4), (4, 7), (4, 8), (5, 8), (7, 10).

Solution:

Chắc sẽ có nhiều bạn (trong đi có mình :<) bị nhầm lẫn giữa đoạn đường có độ dài ít nhất là L với lại đoạn đường có số điểm ít nhất là L. Để ý rằng 2 điểm liên tiếp cách nhau 1 đơn vị vậy một đoạn đường có độ dài ít nhất là L thì phải có ít nhất L + 1 điểm.

Okay sau khi đi qua cái bối rối này rồi thì đến với phần giải bài. Bài này thật chất rất đơn giản sau nhận xét này: Với một điểm cố định i, nếu đoạn đường j → i thỏa thì đoạn đường j + 1 → i cũng thỏa.

Chứng minh thì rất đơn giản, càng đi xa ra khỏi i, min đoạn chỉ có thể giảm cũng như max đoạn cũng chỉ có thể tăng, vậy chênh lệch giữa min và max đoạn càng xa i thì chỉ có thể càng tăng thôi.

Nếu đến đây mà đã nắm được rồi, thì bạn đã có thể bắt tay vào code ngay lúc này :D còn nếu vẫn chưa biết thì đọc tiếp nhé.

Ta có thể tìm điểm j bằng 2 pointers hoặc binary search, điều này rất đơn giản, vậy tìm min và max đoạn j → i trong O(1) hoặc O(logN) thế nào? Để tìm được nhanh ta có thể giải quyết bằng các thuật toán RMQ như Interval Tree, Sparse Table...

Cơ mà code mình thì mình xài deque :) đọc code thì hơi khó hiểu chút cơ mà có thể hiểu đơn giản là thay vì 2 pointers tăng j từ từ lên thì mình tăng j lên thẳng vị trí mà min hoặc max thay đổi, chi tiết thế nào thì coi code ngẫm nhé (không hiểu code thì làm cách dễ hiểu ở trên cũng được, no problem).

Độ phức tạp O(NlogN), cách xài deque của mình thì là O(5N) (lợi hại hem :">)

À có cái này thú vị lắm, cùng một code có thể được 96 điểm hoặc 100 điểm :D nên nếu bạn được 96 điểm thì hãy cứ đè submit nhiều lần là nó 100 à :v

Code:

#include <stdio.h>

#include <queue>

using namespace std;

int n, l, d, a[1000015];

deque <int> dmax, dmin;

long long res;

int main() {

    scanf("%d %d %d", &n, &l, &d);

    for (int i = 1, j = 0; i <= n; i++) {

        scanf("%d", &a[i]);

        while (!dmax.empty() && a[dmax.back()] <= a[i]) dmax.pop_back();

        while (!dmin.empty() && a[dmin.back()] >= a[i]) dmin.pop_back();

        dmax.push_back(i); dmin.push_back(i);

        while (a[dmax.front()] - a[dmin.front()] > d) {

            j = min(dmax.front(), dmin.front());

            if (dmax.front() < dmin.front())

                dmax.pop_front();

            else dmin.pop_front();

        }

        if (i - j > l) res += i - j - l;

    }

    printf("%lld", res);

}