Truy vấn mảng
Đề bài
TRUY VẤN MẢNG
Cho dãy gồm $N$ phần tử $a_1, a_2, \ldots, a_N$. Bạn cần thực hiện $P$ truy vấn, mỗi truy vấn thuộc một trong hai loại sau:
- Loại 1: Dịch chuyển phần tử ở vị trí thứ $N$ về vị trí thứ $1$, các phần tử còn lại dịch sang phải một vị trí;
- Loại 2: Tìm đoạn con độ dài $K$ có nhiều phần tử giá trị bằng $1$ nhất. In ra số lượng phần tử giá trị $1$ trong đoạn tìm được.
Dữ liệu:
- Dòng 1: chứa ba số nguyên $N, K, P$ $(1 \le N, K, P \le 100000)$;
- Dòng 2: chứa $N$ số nguyên $a_1, a_2, \ldots, a_N$ $(0 \le a_i \le 1;\ 1 \le i \le N)$;
- Dòng 3: chứa một xâu bao gồm $P$ ký tự, ký tự thứ $i$ $(1 \le i \le P)$ mô tả truy vấn thứ $i$ với kí tự
'!'mô tả truy vấn loại 1 và kí tự'?'mô tả truy vấn loại 2.
Kết quả: đối với mỗi truy vấn loại 2, in ra một dòng riêng biệt gồm một số nguyên là câu trả lời cho truy vấn tương ứng theo đúng thứ tự đầu vào.
Ràng buộc:
- Subtask 1: 28% số điểm có xâu mô tả truy vấn chỉ bao gồm đúng một kí tự
'?'; - Subtask 2: 07% số điểm có $1 \le N, K, P \le 100$;
- Subtask 3: 09% số điểm có $1 \le N, K, P \le 1000$;
- Subtask 4: 56% số điểm không có thêm ràng buộc bổ sung.
5 4 4
1 0 1 0 1
?!!?2
3Giải thích ví dụ:
- Truy vấn thứ nhất
?: dãy1 0 1 0 1, đoạn dài 4 tốt nhất là[1 0 1 0]có 2 số 1 → in2. - Truy vấn thứ hai
!: dãy trở thành1 1 0 1 0. - Truy vấn thứ ba
!: dãy trở thành0 1 1 0 1. - Truy vấn thứ tư
?: đoạn[1 1 0 1]có 3 số 1 → in3.
Lưu ý: đề cho $1 \le K \le 100000$ nên về lý thuyết $K$ có thể lớn hơn $N$, nhưng mình đã kiểm tra: mọi test đều có $K \le N$, nên không phải xử lý trường hợp đó.
Lời mở đầu
Bài này có hai "chiêu" cần nhận ra. Một là: xoay dãy không cần di chuyển phần tử – chỉ cần nhớ dãy đang bắt đầu ở đâu (xem dãy như một vòng tròn). Hai là: khi xoay, tập các đoạn dài $K$ của dãy chỉ thay đổi một đoạn vào, một đoạn ra – nên ta giữ các đoạn trong một multiset là trả lời ngay được câu hỏi "đoạn nào nhiều số 1 nhất". Cuối bài là cách $O(N + P)$ dùng deque cho bạn nào muốn nâng cao.
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ì?
| Test | N | K | P | Số truy vấn ? |
|---|---|---|---|---|
| 1 – 35 | 1 … 20 | 1 … 15 | 1 … 20 | 1 … 12 |
| 36 – 44 | 1.000 | 145 … 914 | 1.000 | khoảng 500 |
| 45 – 100 | 100.000 | 1.287 … 96.411 | 100.000 | khoảng 50.000 |
- Các test có đúng một dấu
?(subtask 1) đều là test nhỏ ($N \le 20$). Vì vậy "mẹo" chỉ trả lời 1 truy vấn không giúp được gì thêm so với subtask 2. - Ở các test lớn, khoảng một nửa số truy vấn là
?(khoảng 50.000 truy vấn hỏi) và dãy có khoảng một nửa là số 1. - Số truy vấn xoay có thể lớn hơn $N$ (dãy quay hết một vòng rồi quay tiếp) – code phải lấy chỉ số theo modulo $N$.
Mình đối chiếu điều kiện của từng subtask với bộ test thật thì được đúng tỉ lệ 28 / 7 / 9 / 56 test như đề nói:
| Subtask | Điều kiện | Các test | Cách 1 mô phỏng | Cách 2 multiset | Cách 3 deque |
|---|---|---|---|---|---|
| 1 (28%) | đúng một dấu ? | 2–28, 34 | 28/28 | 28/28 | 28/28 |
| 2 (7%) | $N, K, P \le 100$ | 1, 29–33, 35 | 7/7 | 7/7 | 7/7 |
| 3 (9%) | $N, K, P \le 1000$ | 36–44 | 9/9 | 9/9 | 9/9 |
| 4 (56%) | không thêm | 45–100 | 0/56 | 56/56 | 56/56 |
Ý tưởngXem dãy như một vòng tròn
Bước 1 – xoay mà không xoay. Hãy xếp $a_0, a_1, \ldots, a_{N-1}$ (mình đánh số từ 0 cho tiện code) lên một vòng tròn. Thao tác ! không làm thay đổi vòng tròn, nó chỉ dời điểm bắt đầu đọc lùi lại một ô. Gọi dau là chỉ số trong $a$ của phần tử đang đứng đầu dãy: ban đầu dau = 0, mỗi lần ! thì dau = (dau - 1 + N) % N. Dãy hiện tại là $a_{dau}, a_{dau+1}, \ldots$ (đi vòng).
Bước 2 – đoạn vòng tròn. Gọi $c_i$ là số số 1 trong đoạn dài $K$ trên vòng tròn bắt đầu từ $a_i$ (được đi vòng qua cuối dãy). Tính hết $c_0, \ldots, c_{N-1}$ bằng cửa sổ trượt: $c_i = c_{i-1} - a_{i-1} + a_{(i+K-1) \bmod N}$.
Bước 3 – đoạn nào hợp lệ? Trong dãy hiện tại, đoạn dài $K$ bắt đầu ở vị trí $p$ hợp lệ khi $0 \le p \le N - K$ (không bị "gãy" qua chỗ nối cuối–đầu). Vị trí $p$ ứng với $a_{(dau + p) \bmod N}$, nên các đoạn hợp lệ là $c_{dau},$ $c_{dau+1},$ $\ldots,$ $c_{dau+N-K}$ (chỉ số mod $N$) – đúng $N - K + 1$ đoạn liên tiếp trên vòng tròn.
dau lùi 1 ô, khối $N-K+1$ đoạn hợp lệ cũng lùi 1 ô: thêm $c_{dau}$ (đoạn bắt đầu ở đầu dãy mới) và bỏ $c_{(dau + N - K + 1) \bmod N}$ (đoạn trước đây nằm cuối, nay bị gãy). Cất các đoạn hợp lệ trong multiset thì truy vấn ? chỉ là lấy phần tử lớn nhất.Em nhập dãy, $K$ và các truy vấn rồi bấm Tiếp. Hàng dưới là các đoạn $c$ theo vị trí bắt đầu trong dãy hiện tại: ô xanh là đoạn hợp lệ (nằm trong multiset), ô mờ là đoạn bị gãy:
Cách 1Mô phỏng đúng như đề – O(N · P)
Truy vấn !: dời từng phần tử sang phải. Truy vấn ?: dùng cửa sổ trượt tính số số 1 của mọi đoạn dài $K$, lấy lớn nhất. Mỗi truy vấn tốn $O(N)$.
- Vòng
for(int i = n - 1; i > 0; i--)phải chạy từ cuối về đầu, nếu chạy từ đầu thì $a_1$ bị ghi đè trước khi kịp dời đi. Phần tử cuối được cất trước vào biếncuoi. - Cửa sổ trượt: đoạn đầu tiên tính tổng $K$ số, mỗi lần dời cửa sổ thì cộng phần tử mới vào và trừ phần tử vừa ra.
Kết quả chạy thật: bản C++ đúng 44/100 test (quá 1 giây ở các test 45–100), test đúng chạy lâu nhất 0.004s; bản Python đúng 44/100 test (quá thời gian ở các test 45–100), lâu nhất 0.17s. Cách này ăn trọn subtask 1, 2, 3 (44% số điểm). Với $N = P = 10^5$ thì cần cỡ $10^{10}$ phép tính – quá chậm.
Cách 2Đoạn vòng tròn + multiset – O((N + P) log N)
Cài đặt đúng phần ý tưởng: tính mảng $c$, cho $N - K + 1$ đoạn hợp lệ ban đầu ($c_0 \ldots c_{N-K}$) vào multiset, rồi mỗi lần xoay thì thêm một đoạn, bỏ một đoạn.
- Dòng tính $c_0$ là tổng $K$ phần tử đầu; dòng sau trượt cửa sổ trên vòng tròn với chỉ số
(i + k - 1) % nđể đi vòng qua cuối dãy. - Phải dùng
multisetvì nhiều đoạn có cùng số số 1. Khi xoá, dùngms.erase(ms.find(x))để xoá đúng một bản sao củax; viếtms.erase(x)sẽ xoá hết các phần tử bằngx– sai ngay! - Phần tử lớn nhất của multiset là
*ms.rbegin()(phần tử cuối). - Bản Python không có multiset nên mình dùng
heapqvới kỹ thuật xoá lười: phần tử cần xoá chỉ được ghi nhận vào một bộ đếm, khi nó nổi lên đỉnh heap thì mới thật sự bỏ đi.
Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.065s; bản Python đúng 100/100 test, lâu nhất 0.19s.
Cách 3Deque cực đại – O(N + P)
Nhìn kỹ thì khối các đoạn hợp lệ là một cửa sổ độ dài $N - K + 1$ trên vòng $c$, và mỗi lần ! nó trượt đúng 1 ô (về bên trái). Đây chính là bài toán kinh điển "giá trị lớn nhất trên cửa sổ trượt" – giải bằng deque đơn điệu, mỗi phần tử vào/ra deque tối đa một lần.
Để khỏi rối với modulo, mình dùng chỉ số "ảo" $v$ (có thể âm): cửa sổ là $[L, R]$, ban đầu $[0, N - K]$, mỗi lần xoay thì $L$ và $R$ cùng giảm 1; giá trị của chỉ số ảo $v$ là $c_{v \bmod N}$.
- Deque giữ các chỉ số mà giá trị giảm dần từ đầu tới cuối; đầu deque là đoạn tốt nhất. Thêm $v$ mới (bên trái cửa sổ): bỏ hết các phần tử cuối deque có giá trị $\le c_v$ vì chúng vừa "cũ hơn" (sẽ bị đẩy ra trước) vừa không tốt hơn $v$.
- Khi cửa sổ lùi, chỉ số ở đầu deque có thể đã lớn hơn $R$ (bị gãy) → bỏ đi. Chỉ cần kiểm tra một lần vì mỗi bước chỉ có đúng một chỉ số rời cửa sổ.
- Hàm
valviết((v % n) + n) % nđể chỉ số âm cũng về đúng $[0, N)$ (trong C++,-1 % 5 = -1).
Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.022s; bản Python đúng 100/100 test, lâu nhất 0.19s.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất (test đúng) | Ghi chú |
|---|---|---|---|---|
| 1. Mô phỏng | C++ | 44/100 | 0.004s | Quá thời gian ở test 45–100 |
| Python | 44/100 | 0.166s | Quá thời gian ở test 45–100 | |
| 2. Đoạn vòng tròn + multiset | C++ | 100/100 | 0.065s | Full điểm |
| Python (heap xoá lười) | 100/100 | 0.192s | Full điểm | |
| 3. Deque cực đại | C++ | 100/100 | 0.022s | Full điểm |
| Python | 100/100 | 0.187s | Full điểm |
Nhận xét
Đăng nhận xét