1113 - Chụp ảnh cùng thầy Yeh

Gọi đoạn [l, r] là đoạn chứa các phần tử của dãy A từ A_l đến A_r. Với dãy A đề cho, ta sẽ xét một đoạn [l, r] để nắm được ý tưởng bài.

Gọi MAX và MIN lần lượt là số lớn nhất và số nhỏ nhất của đoạn [l, r]:

• Nếu MAX − MIN > K trên đoạn từ [l, r] thì các đoạn [l, r + d] với mọi d ≥ 0, độ chênh lệch giữa số lớn nhất và số bé nhất luôn > K.
• Nếu MAX − MIN \leq K trên đoạn từ [l, r] thì các đoạn [l, r −d] với mọi 0 \leq d \leq r − l, độ chênh lệch giữa số lớn nhất và số bé nhất luôn \leq K.

Vậy nên với mỗi l ∈ [1, N] ta sẽ tìm r lớn nhất mà MAX − MIN của đoạn [l, r] nhỏ hơn hoặc bằng K và ta sẽ cộng thêm r − l + 1 vào đáp án tượng trưng cho các đoạn [l, l], [l, l +1], [l, l +2],..., [l, r] thỏa mãn điều kiện.

Chúng ta sẽ sử dụng binary search để tìm kiếm r và MIN, MAX trên một đoạn bất kì có thể lấy trong O(1) khi sử dụng sparse table.

Độ phức tạp: O(N ·log(N ))