Mảng con 2
Đề bài
SUBARR2 – SUBARRAY 2
Cho một dãy số nguyên $a_1, a_2, \ldots, a_n$ và số nguyên dương $k$.
Dãy con $a_i, a_{i+1}, \ldots, a_j$ $(1 \le i \le j \le n)$ là dãy được tạo từ các phần tử liên tiếp của dãy $A$, bắt đầu từ phần tử $i$ và kết thúc ở phần tử $j$.
Yêu cầu: Cho dãy $a$ và số $k$, tìm số lượng dãy con của $a$ có ít nhất $k$ phần tử khác nhau.
Input:
- Dòng đầu chứa hai số nguyên dương $n, k$ $(1 \le k \le n \le 4 \times 10^5)$.
- Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$ $(a_i \le 10^9)$.
Output: Một dòng duy nhất là số lượng dãy con tìm được.
Giải thích ví dụ: Các dãy con thoả mãn là $a_1 \to a_2$, $a_1 \to a_3$, $a_1 \to a_4$, $a_2 \to a_3$, $a_2 \to a_4$, $a_3 \to a_4$.
Lưu ý trên CLUE OJ: nhập từ bàn phím, in ra màn hình (bảng ví dụ trong đề ghi tên file SUBARR2.INP/SUBARR2.OUT nhưng hệ thống chấm dùng stdin/stdout).
4 2
1 2 1 26Lời mở đầu
Bài này là một bài hai con trỏ (cửa sổ trượt) rất chuẩn mực, kết hợp với map để đếm số giá trị khác nhau trong cửa sổ. Trước khi vào lời giải, các bạn để ý một chi tiết "chết người" của bộ test mà mình phát hiện khi thống kê: các số trong test lớn đều là số âm cỡ $-10^{18}$! Đề chỉ ghi $a_i \le 10^9$ (chặn trên, không chặn dưới), nên ai khai báo int là "toang" ngay.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
Bộ test có 100 test, đề không ghi subtask nên mình tự chia thành 6 mức theo độ lớn của $n$:
| Mức | Test | n lớn nhất | Giá trị $a_i$ | Số giá trị khác nhau | Đáp án lớn nhất | Đáp án = 0 |
|---|---|---|---|---|---|---|
| Mức 1 | 1–20 | 97 | 1 … 40 | ≤ 37 | 1.305 | 6 |
| Mức 2 | 21–40 | 966 | −1,00·1018 … −1,00·1018 | ≤ 951 | 292.958 | 0 |
| Mức 3 | 41–60 | 8.734 | −1,00·1018 … −1,00·1018 | ≤ 7.685 | 27.516.549 | 1 |
| Mức 4 | 61–80 | 37.414 | −1,00·1018 … −1,00·1018 | ≤ 22.309 | 424.045.367 | 4 |
| Mức 5 | 81–90 | 132.702 | −1,00·1018 … −1,00·1018 | ≤ 32.195 | 8.354.476.455 | 1 |
| Mức 6 | 91–100 | 400.000 | −1,00·1018 … −1,00·1018 | ≤ 32.768 | 78.193.716.173 | 0 |
- Giá trị âm khổng lồ: từ test 21 trở đi, mọi $a_i$ nằm trong khoảng $[-10^{18}, -10^{18} + 32767]$. Phải đọc bằng
long long. (Python không bị ảnh hưởng.) - Số giá trị khác nhau tối đa chỉ 32768 dù $n$ tới $4 \cdot 10^5$ – dãy có rất nhiều số lặp lại.
- Đáp án lớn nhất gần $7{,}8 \cdot 10^{10}$ > $2^{31}$ ⇒ biến đếm phải là
long long. Tổng số đoạn con là $\frac{n(n+1)}{2} \approx 8 \cdot 10^{10}$ khi $n = 4 \cdot 10^5$. - Có nhiều test đáp án bằng 0 (khi $k$ lớn hơn số giá trị khác nhau của cả dãy).
Mỗi cách giải ăn được bao nhiêu test ở từng mức (chạy thật):
| Mức | Test | n tới | Cách 1 C++ | Cách 1 Python | Cách 2 C++ | Cách 2 Python | Cách 3 C++ |
|---|---|---|---|---|---|---|---|
| Mức 1 | 1–20 | 97 | 20/20 | 20/20 | 20/20 | 20/20 | 20/20 |
| Mức 2 | 21–40 | 966 | 20/20 | 20/20 | 20/20 | 20/20 | 20/20 |
| Mức 3 | 41–60 | 8.734 | 10/20 | 11/20 | 20/20 | 20/20 | 20/20 |
| Mức 4 | 61–80 | 37.414 | 0/20 | – | 20/20 | 20/20 | 20/20 |
| Mức 5 | 81–90 | 132.702 | 0/10 | – | 10/10 | 10/10 | 10/10 |
| Mức 6 | 91–100 | 400.000 | 0/10 | – | 10/10 | 10/10 | 10/10 |
Ý tưởngĐủ $k$ rồi thì kéo dài thêm vẫn đủ
Nhận xét then chốt: nếu đoạn $[i, j]$ đã có ít nhất $k$ giá trị khác nhau thì mọi đoạn $[i, j'], j' \ge j$ cũng có (thêm phần tử thì số giá trị khác nhau không giảm). Vậy với mỗi đầu trái $i$, gọi $j_i$ là vị trí nhỏ nhất để $[i, j_i]$ đủ $k$ giá trị khác nhau, thì số đoạn bắt đầu tại $i$ thỏa mãn là $n - j_i + 1$.
Nhận xét thứ hai: khi $i$ tăng lên, đoạn mất bớt phần tử bên trái nên $j_i$ không bao giờ lùi lại: $j_{i+1} \ge j_i$. Đây đúng là điều kiện để dùng hai con trỏ:
cnt[v] = số lần $v$ xuất hiện trong cửa sổ, khac = số giá trị có cnt > 0.
Với mỗi $i = 1..n$: nới $j$ sang phải tới khi khac $\ge k$ (hoặc hết dãy); nếu đủ thì cộng $n - j + 1$; rồi bỏ $a_i$ ra khỏi cửa sổ.Mỗi con trỏ chỉ đi tiến, tổng cộng $2n$ bước. Vì $a_i$ rất lớn (và âm) nên cnt phải là map (hoặc nén số trước).
Em nhập $k$ và dãy số rồi bấm Tiếp để xem cửa sổ trượt (vùng xanh là cửa sổ $[i, j]$, các ô gạch chân là các đoạn được đếm):
Cách 1Vét cạn đầu trái, dùng set đếm số khác nhau
Với mỗi $i$, mở rộng $j$ từ $i$ và bỏ $a_j$ vào một set (set tự loại phần tử trùng). Ngay khi kích thước set đạt $k$, cộng $n - j + 1$ và dừng (nhận xét thứ nhất). Cách này đã khôn hơn thử mọi đoạn, nhưng mỗi $i$ vẫn có thể phải đi rất xa.
Kết quả chạy thật: bản C++ đúng 50/100 test (quá giờ ở test 41, 45–48, 52–54, 56, 58, 61–100), test đúng chạy lâu nhất 0.88s; bản Python (chỉ chạy test 1–60) đúng 51/60 test (quá giờ ở test 45–48, 52–54, 56, 58), lâu nhất trên 1s.
Để ý cột "Mức 3" trong bảng: các test quá giờ là các test có $k$ lớn (gần bằng số giá trị khác nhau) – khi đó mỗi $i$ phải đi gần hết dãy mới đủ $k$, đúng là trường hợp xấu $O(n^2 \log n)$.
Cách 2Hai con trỏ + map – Full điểm
jvàkhackhai báo ngoài vòngforcủa $i$ – đó là bí quyết của hai con trỏ: $j$ không quay về.if(cnt[a[j]] == 1) khac++: giá trị $a_j$ vừa xuất hiện lần đầu trong cửa sổ. Ngược lạiif(cnt[a[i]] == 0) khac--: giá trị $a_i$ vừa biến mất khỏi cửa sổ.if(khac < k) break;: đã nới tới $n$ mà vẫn chưa đủ thì với $i$ lớn hơn (cửa sổ còn ít phần tử hơn) càng không đủ – dừng luôn.- Bản Python giữ nguyên các số dạng
bytesđọc được làm khoá củadict(hai số bằng nhau thì chuỗi cũng giống nhau), đỡ tốn thời gian đổi sang số.
Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.42s; bản Python đúng 100/100 test, lâu nhất 0.68s.
Cách 3Nén số + mảng đếm (tăng tốc)
Mỗi thao tác map tốn $O(\log)$ và khá chậm. Ta có thể nén số: sắp xếp và xoá trùng các giá trị, rồi đổi mỗi $a_i$ thành thứ hạng $b_i \in [0, n)$ của nó. Khi đó cnt là một mảng bình thường, truy cập $O(1)$.
Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.18s.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất | Ghi chú |
|---|---|---|---|---|
1. Vét cạn + set | C++ | 50/100 | > 1s | Quá thời gian từ test 41 trở đi (không liên tục) |
| Python | 51/60 | > 1s | Chỉ chạy thử test 1–60; quá thời gian test 45–48, 52–54, 56, 58 | |
2. Hai con trỏ + map | C++ | 100/100 | 0.42s | Full điểm |
| Python | 100/100 | 0.68s | Full điểm (dùng dict) | |
| 3. Nén số + mảng đếm | C++ | 100/100 | 0.18s | Full điểm, nhanh nhất |
int sẽ sai từ test 21. Hai con trỏ với map là đủ full điểm; nén số giúp chạy nhanh hơn khoảng 2 lần.
Nhận xét
Đăng nhận xét