Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Hướng dẫn giải bài

1. Tóm tắt đề bài

Cho mảng \(A\) gồm \(N\) phần tử biểu diễn năng lực của các ứng viên và một số nguyên \(K\). Một đoạn con \([l, r]\) được gọi là hoàn hảo nếu chênh lệch giữa phần tử lớn nhất và nhỏ nhất không vượt quá \(K\):

Có \(Q\) truy vấn, mỗi truy vấn gồm hai số \(L, R\). Bạn cần tìm độ dài lớn nhất của một đoạn con hoàn hảo nằm trọn trong đoạn \([L, R]\).

2. Ý tưởng thuật toán

Bước 1: Tiền xử lý mảng vị trí bắt đầu (Two Pointers)

Nhận xét quan trọng: Với mỗi vị trí kết thúc \(r\), khi dịch \(r\) sang phải thì độ chênh lệch giữa phần tử lớn nhất và nhỏ nhất của đoạn chỉ có thể giữ nguyên hoặc tăng lên. Do đó, vị trí bắt đầu nhỏ nhất \(l\) hợp lệ cho mỗi \(r\) (gọi là \(P[r]\)) sẽ là một dãy không giảm.

Ta sử dụng kỹ thuật Two Pointers (Hai con trỏ) dịch chuyển từ trái sang phải, kết hợp với bảng thưa để kiểm tra điều kiện \(\max - \min \le K\) trong \(O(1)\).

• Ta tính được mảng \(P[r]\) là vị trí trái xa nhất sao cho đoạn \([P[r], r]\) hoàn hảo.
• Từ đó, định nghĩa mảng \(F[r] = r - P[r] + 1\): Độ dài đoạn hoàn hảo dài nhất kết thúc tại \(r\) trên toàn mảng.

Bước 2: Dựng các bảng thưa (Sparse Table)

Để tối ưu thời gian phản hồi truy vấn, ta dựng 3 bảng thưa:

1. mx[i][j] và mn[i][j]: Tìm \(\max\) và \(\min\) của mảng \(A\) phục vụ cho thuật toán hai con trỏ ở Bước 1.
2. f[i][j]: Tìm giá trị lớn nhất của mảng \(F\) trên một đoạn bất kỳ trong \(O(1)\).

Bước 3: Xử lý truy vấn \([L, R]\) bằng Chặt nhị phân

Với một truy vấn \([L, R]\), ta không thể lấy trực tiếp \(\max(F[i])\) với mọi \(i \in [L, R]\) vì có khả năng một số vị trí \(i\) có đoạn hoàn hảo dài nhất bị tràn ra ngoài biên trái \(L\) (tức là \(P[i] < L\)).

Vì mảng \(P\) là mảng tăng dần, ta sử dụng Chặt nhị phân (Binary Search) để tìm vị trí \(ans\) lớn nhất thuộc đoạn \([L, R]\) sao cho \(P[ans] \le L\). Khi đó, đoạn truy vấn \([L, R]\) được chia thành hai phần:

• Phần 1 (Từ \(L\) đến \(ans\)): Các vị trí \(i\) này đều có \(P[i] \le L\). Đoạn hoàn hảo dài nhất kết thúc tại \(i\) nhưng nằm trong \([L, R]\) sẽ bị giới hạn ở \(L\), có độ dài là \(i - L + 1\). Giá trị lớn nhất của phần này luôn đạt được tại \(ans\), bằng \(ans - L + 1\).
• Phần 2 (Từ \(ans + 1\) đến \(R\)): Các vị trí \(i\) này đều có \(P[i] > L\). Đoạn hoàn hảo kết thúc tại \(i\) đã nằm trọn vẹn ở bên phải \(L\). Ta chỉ cần truy vấn tìm \(\max(F[i])\) trong đoạn \([ans + 1, R]\) bằng bảng thưa.

Kết quả của truy vấn chính là \(\max(ans - L + 1, \max_{i=ans+1}^{R} F[i])\).

3. Đánh giá độ phức tạp

• Thời gian (Time Complexity): * Tiền xử lý (Two Pointers & Bảng thưa): \(O(N \log N)\).
• Mỗi truy vấn: \(O(\log N)\) cho thao tác chặt nhị phân, còn RMQ lấy kết quả trong \(O(1)\).
• Tổng thời gian xử lý: \(O((N + Q) \log N)\), chạy cực mượt trong giới hạn 1.0 giây với \(N, Q \le 2 \cdot 10^5\).
• Bộ nhớ (Space Complexity): \(O(N \log N)\) phục vụ lưu trữ trạng thái của các bảng thưa Sparse Table.

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N = 200005;
const int M = 19;
int n, k, q;
int a[N], p[N], g[N], f[N][M];

int h(int l, int r) {
    if (l > r) return 0;
    int j = g[r - l + 1];
    return max(f[l][j], f[r - (1 << j) + 1][j]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (!(cin >> n >> k >> q)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    g[1] = 0;
    for (int i = 2; i <= n; i++) g[i] = g[i / 2] + 1;
    deque<int> d, e;
    int l = 1;
    for (int r = 1; r <= n; r++) {
        while (!d.empty() && a[d.back()] <= a[r]) d.pop_back();
        d.push_back(r);
        while (!e.empty() && a[e.back()] >= a[r]) e.pop_back();
        e.push_back(r);
        while (a[d.front()] - a[e.front()] > k) {
            l++;
            if (d.front() < l) d.pop_front();
            if (e.front() < l) e.pop_front();
        }
        p[r] = l;
    }
    for (int i = 1; i <= n; i++) f[i][0] = i - p[i] + 1;
    for (int j = 1; j < M; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
    while (q--) {
        int u, v;
        cin >> u >> v;
        int x = u, y = v, z = u - 1;
        while (x <= y) {
            int m = x + (y - x) / 2;
            if (p[m] <= u) {
                z = m;
                x = m + 1;
            } else {
                y = m - 1;
            }
        }
        cout << max(z - u + 1, h(z + 1, v)) << "\n";
    }
    return 0;
}