TS10 Thanh Hóa 2026 - Đoạn con đặc biệt
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Cho dãy số nguyên ~A~ gồm ~N~ phần tử ~A_1, A_2, \dots, A_N~. Lam định nghĩa một đoạn con liên tiếp ~A_i, A_{i+1}, \dots, A_j~ (với ~1 \le i \le j \le N~) là đoạn con đặc biệt nếu thỏa mãn đồng thời các điều kiện sau:
Tất cả các phần tử trong đoạn đôi một khác nhau (không có số nào lặp lại).
Hiệu giữa phần tử lớn nhất và nhỏ nhất trong đoạn không vượt quá ~X~. Nghĩa là: $$\max\{A_i, A_{i+1}, \dots, A_j\} - \min\{A_i, A_{i+1}, \dots, A_j\} \le X$$
Yêu cầu: Bạn hãy giúp Lam đếm số lượng đoạn con đặc biệt trong dãy ~A~.
Input
Dòng đầu tiên chứa hai số nguyên ~N, X~ ~(1 \le N \le 5 \cdot 10^6; 0 \le X \le 2 \cdot 10^6)~.
Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, \dots, A_N~ ~(|A_i| \le 10^6; i = 1 \dots N)~.
Output
Số lượng đoạn con đặc biệt.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~20\%~ | ~1 \le N \le 5 \cdot 10^2~ và các phần tử của dãy ~A~ đôi một khác nhau |
| 2 | ~20\%~ | ~5 \cdot 10^2 < N \le 5 \cdot 10^3~ |
| 3 | ~40\%~ | ~5 \cdot 10^3 < N \le 5 \cdot 10^5~ |
| 4 | ~20\%~ | Không có ràng buộc gì thêm |
Sample Input 1
4 3
2 -3 2 1
Sample Output 1
5
Notes
Có ~5~ đoạn con thỏa mãn: ~\{2\}; \{-3\}; \{2\}; \{1\}; \{2, 1\}~
Bình luận
Video giải đề: https://www.youtube.com/live/9MXrh3p8YvM
Xem lời giải và code mẫu trong phần mô tả của video
2 con trỏ kết hợp deque
dạ
dạ