\(\color{#ff0000}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.5}}}}}\)

\(\color{#ff0000}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{#ff0000}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{#ff0000}{\text{Mình xin rút kinh nghiệm và chấn chỉnh bản thân nếu trong editorial có gì sai sót, và bạn có thể gửi feedback }}\) ở đây

\(\color{#300000}{\text{Hint 1 <Cày Trâu>}}\)

Duyệt tuần tự các đoạn con và dùng Segment tree để tính min, max cho từng đoạn.

Độ phức tạp thời gian tổng thể của cách này sẽ là \(O(n^2 * log(n))\)

\(\color{#300000}{\text{Hint 2 + 3 <Two - Pointer>}}\)

Như ta thấy nếu càng tăng độ dài đoạn con thì khoảng cách giữa min và max sẽ càng tăng. Dựa vào điều nào ta có thể áp dụng 2 con trỏ; kết hợp với heap hoặc set để tìm min, max.

• Giả sử cho trỏ i chạy trước còn trỏ j chạy từ 1 theo sau.

• Khi nào ta thấy đoạn j đến còn có max - min > k thì cộng j.

• Nếu đoạn j đến i thỏa mãn điều kiện thì ta sẽ lấy số lượng vị trí từ j đến max( mp[min], mp[max] ) ( mp là vị trí xuất hiện cuối cùng).

Độ phức tạp thời gian tổng thể của cách này sẽ là \(O(n * log(n))\)

\(\color{#009933}{\text{Preference Accepted Code }}\):

 for( int i=1; i<=n; i++ )
    {
        mp[a[i]] = i;

        s.insert(a[i]);

        // cho j ban đầu bằng 1 và chạy theo i

        //*s.rbegin() là max, *s.begin() là min

        for(;j<i, *s.rbegin() - *s.begin()>k; j++)
            s.erase(s.find(a[j]));

        // khi nào đoạn j đến i có max-min > k thì tăng j và xóa a[j] trong set

        if( *s.rbegin() -   *s.begin()  ==  k) // nếu thỏa mãn điều kiện
            ans + = ( min ( mp[*s.begin()], mp[*s.rbegin()] ) - j + 1 );

        //lấy vị trí xuất hiện cuối cùng của min, và max
    }