Đếm đoạn con 2
Đề bài
Cho mảng số nguyên dương gồm $n$ phần tử $a_1, a_2, \ldots, a_n$.
Một đoạn con liên tiếp của dãy $a$ được xác định bởi hai chỉ số $l, r$ tức là các phần tử $a_l, a_{l+1}, \ldots, a_r$.
Nhiệm vụ của bạn là đếm số lượng đoạn con có nhiều nhất $k$ phần tử khác nhau.
Dữ liệu vào:
- Dòng đầu tiên chứa $n, k$ $(1 \le k \le n \le 2 \cdot 10^5)$;
- Dòng thứ hai chứa $n$ số nguyên dương $a_1, a_2, \ldots, a_n$ $(a_i \le 10^9)$.
Kết quả ra: in ra một số nguyên dương là số lượng đoạn con thỏa mãn yêu cầu của đề bài.
Ràng buộc:
- Subtask 1: 30% số test $n \le 100$;
- Subtask 2: 30% số test $n \le 1000$; $a_i \le 1000$;
- Subtask 3: 20% số test $a_i \le 10^6$;
- Subtask 4: 20% số test còn lại không có ràng buộc gì.
Giới hạn: 1 giây, 256 MB.
5 2
1 2 3 1 110Giải thích ví dụ: với $k = 2$, dãy 1 2 3 1 1 có 15 đoạn con. Các đoạn có tới 3 giá trị khác nhau là [1 2 3], [1 2 3 1], [1 2 3 1 1], [2 3 1], [2 3 1 1] – 5 đoạn. Còn lại $15 - 5 = 10$ đoạn thoả mãn.
Lời mở đầu
Đây là một bài rất "kinh điển" của chủ đề Map/Set kết hợp kỹ thuật hai con trỏ (cửa sổ trượt). Đề chia 4 subtask rất rõ ràng nên mình sẽ đi đúng theo lộ trình đó: từ vét cạn ăn subtask 1, rồi tối ưu dần lên tới full điểm. Mỗi cách mình đều chạy thật trên toàn bộ 100 test của CLUE OJ và ghi lại kết quả để các bạn thấy rõ vì sao cách đó qua được subtask này mà không qua được subtask kia.
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 gồm 100 test. Mình thống kê theo từng nhóm:
| Nhóm test | Số test | n | k | ai lớn nhất | Số giá trị khác nhau (max) | Đáp án lớn nhất |
|---|---|---|---|---|---|---|
| 1–30 | 30 | 5 – 100 | 1 – 10 | 20 | 20 | 1.326 |
| 31–60 | 30 | 1.000 – 1.000 | 5 – 344 | 999 | 394 | 490.927 |
| 61–80 | 20 | 200.000 – 200.000 | 1.160 – 32.408 | 999.999 | 70.627 | 12.389.421.145 |
| 81–100 | 20 | 200.000 – 200.000 | 370 – 31.835 | 999.999.489 | 117.817 | 8.538.282.141 |
Đối chiếu với đề thì các test được xếp đúng thứ tự subtask:
| Subtask | Điều kiện (theo đề) | Test | Thực tế trong bộ test |
|---|---|---|---|
| 1 (30%) | $n \le 100$ | 1 – 30 | test 1–20: $n \le 10$; test 21–30: $n = 100$, $a_i \le 20$ |
| 2 (30%) | $n \le 1000$, $a_i \le 1000$ | 31 – 60 | $n = 1000$, $a_i \le 999$ |
| 3 (20%) | $a_i \le 10^6$ | 61 – 80 | $n = 2 \cdot 10^5$, $a_i < 10^6$ |
| 4 (20%) | không ràng buộc thêm | 81 – 100 | $n = 2 \cdot 10^5$, $a_i$ tới gần $10^9$ |
int. Trong bộ test có 36 test có đáp án lớn hơn $2^{31} - 1$, nên biến đếm bắt buộc phải là long long.Ý tưởngNhận xét then chốt: đoạn càng ngắn càng "ít khác nhau"
Gọi $d(l, r)$ là số giá trị khác nhau trong đoạn $[l, r]$. Có hai tính chất rất tự nhiên:
- Kéo dài đoạn (tăng $r$) thì $d$ chỉ có thể tăng hoặc giữ nguyên.
- Cắt bớt đầu trái (tăng $l$) thì $d$ chỉ có thể giảm hoặc giữ nguyên.
Hệ quả: nếu đoạn $[l, r]$ thoả mãn ($d \le k$) thì mọi đoạn con nằm trong nó cũng thoả mãn. Vậy với mỗi đầu phải $r$, nếu gọi $l$ là vị trí nhỏ nhất sao cho $[l, r]$ còn thoả mãn, thì có đúng $r - l + 1$ đoạn kết thúc tại $r$ thoả mãn: $[l, r], [l+1, r], \ldots, [r, r]$.
Để biết cửa sổ có bao nhiêu giá trị khác nhau, ta giữ một bảng đếm cnt[x] = số lần $x$ xuất hiện trong cửa sổ. Số giá trị khác nhau chính là số khoá $x$ có cnt[x] > 0. Với map, khi cnt[x] về 0 ta erase luôn, khi đó cnt.size() chính là số giá trị khác nhau.
Em nhập dãy rồi bấm Tiếp để xem cửa sổ trượt (ô xanh tím là cửa sổ $[l, r]$, ô viền cam là phần tử vừa vào):
Cách 1Vét cạn mọi đoạn, dùng set đếm giá trị khác nhau – Subtask 1
Cách "thật thà" nhất: duyệt mọi cặp $(l, r)$, với mỗi đoạn thì bỏ hết các phần tử vào một set (set tự loại phần tử trùng), kích thước set chính là số giá trị khác nhau. Có $\frac{n(n+1)}{2}$ đoạn, mỗi đoạn tốn tới $O(n \log n)$ để dựng set.
set<int> skhai báo bên trong vòngrnên mỗi đoạn được dựng lại từ đầu – đơn giản, dễ đúng, nhưng rất chậm.(int)s.size(): ép kiểu để so sánh vớiint kkhông bị cảnh báo so sánh có dấu/không dấu.anslàlong longngay từ cách đầu tiên cho quen tay.
Kết quả chạy thật: bản C++ đúng 30/100 test – ăn trọn Subtask 1; sai mọi test từ test 31 trở đi (quá thời gian); test đúng chậm nhất chạy dưới 0,01s. Bản Python đúng 30/100 test – ăn trọn Subtask 1; sai mọi test từ test 31 trở đi (quá thời gian); test đúng chậm nhất chạy 0,03s. Với $n = 1000$ đã cần khoảng $1.7 \cdot 10^8$ lần chèn vào set nên subtask 2 trở đi đều quá thời gian.
Cách 2Cố định đầu trái, kéo dài đầu phải với mảng đếm – Subtask 1, 2
Cách 1 lãng phí ở chỗ: đoạn $[l, r+1]$ chỉ hơn đoạn $[l, r]$ đúng một phần tử $a_{r+1}$, vậy mà ta lại dựng set từ đầu. Ta sửa lại: cố định $l$, cho $r$ chạy tăng dần và cập nhật dần số giá trị khác nhau $d$: khi đưa $a_r$ vào, nếu cnt[a[r]] vừa từ 0 lên 1 thì đó là giá trị mới, $d$ tăng 1.
Thêm nữa, theo nhận xét ở phần ý tưởng, khi $d > k$ thì kéo dài thêm cũng vô ích → break luôn. Subtask 2 có $a_i \le 1000$ nên dùng thẳng mảng cnt[1005] làm bảng đếm, không cần set/map.
memset(cnt, 0, sizeof(cnt))mỗi lần đổi $l$: chỉ tốn 1005 phép gán, với $n = 1000$ là khoảng $10^6$ – không đáng kể.- Câu
if(d > k) break;đặt trướcans++: đoạn vừa vượt quá $k$ thì không được đếm. - Mảng
cntchỉ có 1005 ô nên cách này không dùng được khi $a_i$ lớn (subtask 3, 4 sẽ truy cập ngoài mảng).
Kết quả chạy thật: bản C++ đúng 60/100 test – ăn trọn Subtask 1, Subtask 2; sai mọi test từ test 61 trở đi (lỗi chạy); test đúng chậm nhất chạy dưới 0,01s. Bản Python đúng 60/100 test – ăn trọn Subtask 1, Subtask 2; sai mọi test từ test 61 trở đi (lỗi chạy); test đúng chậm nhất chạy 0,18s. Từ subtask 3, $n = 2 \cdot 10^5$ và $a_i$ vượt 1000 nên vừa chậm $O(n^2)$, vừa truy cập ngoài mảng.
Cách 3Hai con trỏ với mảng đếm – Subtask 1, 2, 3
Bây giờ áp dụng đúng ý tưởng hai con trỏ: không "reset" lại khi đổi $l$ nữa mà cả $l$ lẫn $r$ cùng tiến về phía trước. Subtask 3 có $a_i \le 10^6$ nên mảng đếm 1 triệu ô vẫn vừa bộ nhớ (4 MB).
- Vòng
while(d > k): mỗi lần lặp đưa $a_l$ ra khỏi cửa sổ; nếu đếm của nó về 0 thì cửa sổ mất một giá trị khác nhau. ans += r - l + 1: sau vòngwhile, $l$ là đầu trái nhỏ nhất hợp lệ cho đầu phải $r$, nên có đúng $r - l + 1$ đoạn kết thúc tại $r$ thoả mãn.- Con trỏ $l$ chỉ tăng, tổng số lần chạy
whiletrong cả chương trình không quá $n$ → $O(n)$.
Kết quả chạy thật: bản C++ đúng 80/100 test – ăn trọn Subtask 1, Subtask 2, Subtask 3; sai mọi test từ test 81 trở đi (lỗi chạy); test đúng chậm nhất chạy 0,03s. Bản Python đúng 80/100 test – ăn trọn Subtask 1, Subtask 2, Subtask 3; sai mọi test từ test 81 trở đi (lỗi chạy); test đúng chậm nhất chạy 0,18s. Subtask 4 có $a_i$ tới $10^9$ thì không thể khai báo mảng đếm $10^9$ ô (4 GB) nên bị lỗi.
Cách 4Hai con trỏ với map – Full điểm
Vấn đề duy nhất còn lại là giá trị quá lớn để làm chỉ số mảng. Đây đúng là lúc dùng map<int, int>: map chỉ lưu những giá trị đang có mặt trong cửa sổ (tối đa $k + 1$ khoá), giá trị lớn tới đâu cũng được. Khi đếm của một khoá về 0 thì erase nó đi, nhờ vậy cnt.size() luôn bằng đúng số giá trị khác nhau – không cần biến $d$ riêng nữa.
cnt[a[r]]++: nếu khoá chưa có,maptự tạo với giá trị 0 rồi tăng lên 1.- Bắt buộc phải
cnt.erase(a[l])khi đếm về 0. Nếu quên, khoá vẫn nằm trong map với giá trị 0,cnt.size()sẽ đếm cả nó và cho kết quả sai. - Mỗi thao tác trên map tốn $O(\log k)$, cả chương trình $O(n \log k)$.
Kết quả chạy thật: bản C++ đúng 100/100 test – ăn trọn Subtask 1, Subtask 2, Subtask 3, Subtask 4; test đúng chậm nhất chạy 0,18s. Bản Python dùng dict (bảng băm) đúng 100/100 test – ăn trọn Subtask 1, Subtask 2, Subtask 3, Subtask 4; test đúng chậm nhất chạy 0,24s.
Tổng kếtKết quả chạy thật của các cách
| Cách | Subtask 1 test 1–30 | Subtask 2 test 31–60 | Subtask 3 test 61–80 | Subtask 4 test 81–100 | Tổng | Chậm nhất (test đúng) |
|---|---|---|---|---|---|---|
| Cách 1 – C++ | 30/30 | 0/30 quá thời gian | 0/20 quá thời gian | 0/20 quá thời gian | 30/100 | 0,01s |
| Cách 1 – Python | 30/30 | 0/30 quá thời gian | 0/20 quá thời gian | 0/20 quá thời gian | 30/100 | 0,03s |
| Cách 2 – C++ | 30/30 | 30/30 | 0/20 lỗi chạy | 0/20 lỗi chạy | 60/100 | 0,00s |
| Cách 2 – Python | 30/30 | 30/30 | 0/20 lỗi chạy | 0/20 lỗi chạy | 60/100 | 0,18s |
| Cách 3 – C++ | 30/30 | 30/30 | 20/20 | 0/20 lỗi chạy | 80/100 | 0,03s |
| Cách 3 – Python | 30/30 | 30/30 | 20/20 | 0/20 lỗi chạy | 80/100 | 0,18s |
| Cách 4 – C++ | 30/30 | 30/30 | 20/20 | 20/20 | 100/100 | 0,18s |
| Cách 4 – Python | 30/30 | 30/30 | 20/20 | 20/20 | 100/100 | 0,24s |
g++ -O2), mỗi lần chạy bị giới hạn CPU và bộ nhớ như máy chấm. Cách 4 bản C++ đạt 100/100 test. Python chậm hơn C++ nhiều lần; bạn nào nộp Python mà bị sát giới hạn thì nên chọn PyPy nếu hệ thống cho phép.
Nhận xét
Đăng nhận xét