Elearning CodePath – CTP Online Judge

Thống kê (statis.*)

191-THN

🟢 Hard #General #Tree #Sorting

## 💻 Đề Bài:

### 📌 **Thông tin chương trình**

---

### 📝 **Bài toán**

Cho số nguyên dương $N$ và dãy số nguyên dương $A = (A_1, A_2, \dots, A_N)$. Các số trong dãy đôi một khác nhau.

Với một số $k$ cho trước, xét tất cả các **đoạn con** (dãy gồm $L$ phần tử liên tiếp) có độ dài $L$. Với mỗi đoạn con, ta lấy ra **phần tử lớn thứ $k$** ($k$-th largest element).

Yêu cầu là tìm **$Y_k$** là **số lớn nhất** trong tất cả các số (phần tử lớn thứ $k$) được lấy ra.

Cho $Q$ truy vấn, mỗi truy vấn mô tả bằng số nguyên $k$, hãy tìm $Y_k$.

### 📥 **Định dạng Input**

* **Dòng 1:** Chứa ba số nguyên dương $N, L, Q$ ($1 \le L \le N \le 2 \cdot 10^5$, $1 \le Q \le 2 \cdot 10^5$).
* **Dòng 2:** Gồm $N$ số nguyên $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^9$).
* **Dòng 3:** Gồm $Q$ số, mỗi số mô tả một truy vấn $k$ ($1 \le k \le L$).

**Giới hạn:**
$$1 \le L \le N \le 2 \cdot 10^5$$
$$1 \le Q \le 2 \cdot 10^5$$
$$1 \le A_i \le 10^9$$
$$1 \le k \le L$$

### 📤 **Định dạng Output**

Gồm một dòng chứa $Q$ số, mỗi số là câu trả lời $Y_k$ của truy vấn tương ứng.

### ✨ **Ví dụ**

| Input | Output |
| :--- | :--- |
| **10 3 3** | **8 10 9** |
| 1 10 9 8 2 3 4 5 6 7 | |
| 1 3 2 | |

#### **Subtask 1: $N, Q$ nhỏ ( $N \le 5000$ và $Q$ nhỏ)**

* **Thuật toán:**
    * Sử dụng vòng lặp $O(N)$ để duyệt qua tất cả các đoạn con độ dài $L$.
    * Trong mỗi đoạn con, sao chép $L$ phần tử, sắp xếp $O(L \log L)$, và lấy phần tử thứ $k$.
    * Lặp lại cho mỗi truy vấn $Q$.
* **Độ phức tạp:** $O(Q \cdot N \cdot L \log L)$. (Quá chậm nếu $N, Q$ lớn)

#### **Subtask 2: $N, Q$ lớn ($N, Q \le 2 \cdot 10^5$)**

Để đạt được độ phức tạp hiệu quả hơn (thường là $O(N \log N)$ hoặc $O((N+Q) \log N)$), ta cần xử lý hiệu quả.

1. * Sử dụng **Cửa sổ trượt (Sliding Window)** kết hợp với **Cây phân đoạn (Segment Tree)** hoặc **Cây Fenwick (BIT)**

2.  **Tối ưu hóa $Q$ truy vấn (Giảm truy vấn về $k$):**
       * Sử dụng **Tìm kiếm nhị phân (Binary Search)** trên tập hợp các giá trị $A_i$ để tìm $Y_k$.
        * Sử dụng **Cửa sổ trượt** $O(1)$ hoặc **Tổng tiền tố** $O(N)$ để kiểm tra điều kiện $\ge k$.
    * **Độ phức tạp:** $O(N \log N)$

✅ Đã AC: 0 / 0 submissions