Biến đổi xâu (Tin học trẻ toàn quốc 2022 – Vòng sơ khảo – Bảng C1, C2)
Đề bài
Cho xâu $s$ độ dài $n$ chỉ gồm chữ cái in thường, các kí tự đánh số từ $0$ tới $n - 1$. Lần lượt thực hiện $m$ thao tác, mỗi thao tác có dạng $(i, j, c_1, c_2)$: mọi vị trí trong đoạn $[i, j]$ đang chứa chữ $c_1$ được đổi thành chữ $c_2$ (các vị trí khác giữ nguyên).
Yêu cầu: in xâu thu được sau khi thực hiện xong tất cả các thao tác theo đúng thứ tự.
Dữ liệu vào:
- Dòng đầu: xâu $s$ ($1 \le n \le 10^6$), chỉ gồm chữ cái in thường;
- Dòng thứ hai: số nguyên $m$ ($1 \le m \le 1{,}5 \cdot 10^5$);
- $m$ dòng tiếp theo, mỗi dòng gồm $i, j, c_1, c_2$ ($0 \le i \le j < n$; $c_1 \ne c_2$ là chữ cái in thường), cách nhau bởi dấu cách.
Kết quả: xâu $s$ sau $m$ thao tác.
Subtask (mỗi subtask 20% số điểm):
- Subtask 1: $n, m \le 2000$;
- Subtask 2: $n, m \le 5 \cdot 10^4$;
- Subtask 3: $n \le 3 \cdot 10^5$;
- Subtask 4: các kí tự trong xâu và trong các thao tác chỉ là
ahoặcb; - Subtask 5: không có ràng buộc gì thêm.
Giới hạn thời gian: 1 giây. Dữ liệu nhập từ bàn phím, in ra màn hình.
aaaabbbbcccc
3
0 2 a y
5 9 b c
1 3 a zyyyzbcccccccGiải thích: sau thao tác 1 (đổi a thành y trong đoạn $[0, 2]$): yyyabbbbcccc; sau thao tác 2 (đổi b thành c trong $[5, 9]$): yyyabccccccc; sau thao tác 3 (đổi a thành z trong $[1, 3]$): yyyzbccccccc.
Lời mở đầu
Làm đúng như đề thì mỗi thao tác tốn $O(n)$, tổng $O(nm) = 1{,}5 \cdot 10^{11}$ – quá chậm. Khó khăn là thao tác không đồng nhất: trong cùng một đoạn, ô chứa $c_1$ thì đổi, ô khác thì không, nên không "gán đoạn" như bình thường được. Mấu chốt: hãy coi mỗi thao tác là một hàm số trên 26 chữ cái $g(x)$ = "$c_2$ nếu $x = c_1$, ngược lại $x$". Áp nhiều thao tác liên tiếp lên một ô chính là hợp các hàm đó – và hợp của các hàm trên 26 chữ cái vẫn chỉ là một bảng 26 ô. Từ đó ta có thể "ghi nợ" thao tác cho cả một khối (chia căn) hay một nút (cây phân đoạn lazy).
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 có gì?
Bộ test trên CLUE do mình tự sinh theo đúng giới hạn và tỉ lệ điểm subtask của đề: 20 test, mỗi subtask 4 test (test 1 là ví dụ của đề, test 2 có $n = 1$). Các thao tác có đoạn ngẫu nhiên, đoạn rất dài (gần cả xâu), đoạn rất ngắn (test 12: độ dài trung bình 3), bảng chữ cái nhỏ (2–6 chữ – thao tác đổi qua đổi lại liên tục) lẫn đủ 26 chữ.
| Test | Subtask | $n$ | $m$ | Số chữ cái dùng | Độ dài đoạn trung bình |
|---|---|---|---|---|---|
| 1 | 1 | 12 | 3 | 5 | 4 |
| 2 | 1 | 1 | 1 | 2 | 1 |
| 3 | 1 | 2.000 | 2.000 | 4 | 876 |
| 4 | 1 | 2.000 | 2.000 | 26 | 716 |
| 5 | 2 | 50.000 | 50.000 | 26 | 16.617 |
| 6 | 2 | 50.000 | 50.000 | 3 | 21.951 |
| 7 | 2 | 50.000 | 50.000 | 26 | 43.727 |
| 8 | 2 | 49.999 | 50.000 | 6 | 8.301 |
| 9 | 3 | 300.000 | 150.000 | 26 | 99.960 |
| 10 | 3 | 300.000 | 150.000 | 5 | 161.910 |
| 11 | 3 | 300.000 | 150.000 | 3 | 133.197 |
| 12 | 3 | 200.000 | 150.000 | 26 | 3 |
| 13 | 4 | 1.000.000 | 150.000 | 2 | 333.721 |
| 14 | 4 | 1.000.000 | 150.000 | 2 | 874.902 |
| 15 | 4 | 1.000.000 | 150.000 | 2 | 4 |
| 16 | 4 | 999.999 | 149.999 | 2 | 521.243 |
| 17 | 5 | 1.000.000 | 150.000 | 26 | 332.596 |
| 18 | 5 | 1.000.000 | 150.000 | 26 | 696.494 |
| 19 | 5 | 1.000.000 | 150.000 | 4 | 360.259 |
| 20 | 5 | 1.000.000 | 150.000 | 26 | 361.373 |
Kết quả chạy thật các cách bên dưới theo từng subtask (ô xanh = đúng hết các test của subtask đó):
| Subtask | Điều kiện | Test | Cách 1 C++ | Cách 1 Python | Cách 2 C++ | Cách 2 Python | Cách 3 C++ | Cách 4 C++ | Cách 4 Python |
|---|---|---|---|---|---|---|---|---|---|
| Subtask 1 (20%) | $n, m \le 2000$ | 1–4 | 4/4 | 4/4 | 4/4 | 4/4 | 4/4 | 4/4 | 4/4 |
| Subtask 2 (20%) | $n, m \le 5 \cdot 10^4$ | 5–8 | 2/4 | 0/4 | 4/4 | 0/4 | 4/4 | 4/4 | 0/4 |
| Subtask 3 (20%) | $n \le 3 \cdot 10^5$ | 9–12 | 1/4 | 1/4 | 1/4 | 1/4 | 4/4 | 4/4 | 0/4 |
| Subtask 4 (20%) | chỉ có chữ a, b | 13–16 | 1/4 | 1/4 | 1/4 | 1/4 | 4/4 | 4/4 | 0/4 |
| Subtask 5 (20%) | không ràng buộc thêm | 17–20 | 0/4 | 0/4 | 0/4 | 0/4 | 4/4 | 4/4 | 0/4 |
Ý tưởngThao tác là một ánh xạ 26 chữ cái
Thao tác $(i, j, c_1, c_2)$ áp lên mỗi ô trong $[i, j]$ cùng một hàm $g$: $g(c_1) = c_2$, $g(x) = x$ với $x \ne c_1$. Nếu một nhóm ô cùng chịu các thao tác $g_1, g_2, \dots, g_t$ (theo thứ tự) thì ô nào ban đầu là chữ $x$ cuối cùng sẽ thành $g_t(\dots g_2(g_1(x)))$. Ta lưu hàm hợp $F = g_t \circ \dots \circ g_1$ dưới dạng bảng $F[x]$ với 26 ô, và cập nhật khi có thao tác mới phủ trọn nhóm: $F[x] \leftarrow g(F[x])$, tức là "ô nào đang (thực tế) là $c_1$ thì thành $c_2$": duyệt 26 chữ $x$, chỗ nào $F[x] = c_1$ thì đặt $F[x] = c_2$.
Chia căn: cắt xâu thành các khối dài $B$, mỗi khối giữ một bảng $F$. Thao tác trên $[i, j]$: các khối nằm trọn trong đoạn chỉ cần sửa bảng $F$ của khối; hai khối ở hai đầu (phủ một phần) thì "trả nợ" – áp $F$ xuống từng ô, đặt lại $F$ đồng nhất – rồi làm tay từng ô.
Em nhập xâu và các thao tác (mỗi thao tác "i j c1 c2", cách nhau bởi dấu ;), khối dài $B$, rồi bấm Tiếp:
a, b, thao tác "đổi $c_1$ thành $c_2$ trên $[i, j]$" làm mọi ô của đoạn thành $c_2$ (ô nào khác $c_1$ thì vốn đã là $c_2$). Đó là phép gán đoạn: chữ cuối cùng của ô $p$ là $c_2$ của thao tác cuối cùng phủ $p$. Duyệt thao tác từ cuối về đầu, tô các ô chưa tô (dùng DSU "nhảy tới ô chưa tô kế tiếp") là xong trong $O(n + m)$. Các cách tổng quát bên dưới đều tự nhiên ăn luôn subtask này.Cách 1Làm đúng như đề (Subtask 1)
Mỗi thao tác duyệt các ô từ $i$ tới $j$ và đổi những ô đang là $c_1$.
Kết quả chạy thật: Bản C++ đúng 8/20 test, quá thời gian test 6–7, 9–11, 13–14, 16–20 (các test đúng chạy lâu nhất 0.607s). Ăn trọn subtask 1, và qua được vài test khác có đoạn ngắn (test 8: độ dài đoạn trung bình khoảng 8000, test 12: 3, test 15: 4). Bản Python đúng 6/20 test, quá thời gian test 5–11, 13–14, 16–20 (các test đúng chạy lâu nhất 0.168s).
Cách 2Chia căn, mỗi khối một bảng ánh xạ (Subtask 1, 2)
Cài đúng ý tưởng chia căn với $B = \lfloor \sqrt{n} \rfloor$. Trong xâu s ta lưu chữ "gốc" của khối (chữ trước khi áp bảng $F$); chữ thật sự ở ô $p$ là f[b][s[p]].
day(b): áp bảng của khối $b$ xuống từng ô, đặt lại bảng đồng nhất – $O(B + 26)$. Phải gọi trước khi làm tay trên khối, vì phần làm tay so sánh với chữ thật.- Khối nằm trọn: sửa 26 ô của bảng – $O(26)$, không đụng tới xâu.
- Mỗi thao tác tốn khoảng $4B + 26 \cdot n / B$ phép.
Kết quả chạy thật: Bản C++ đúng 10/20 test, quá thời gian test 9–11, 13–14, 16–20 (các test đúng chạy lâu nhất 0.266s). Với $n = 3 \cdot 10^5$, $m = 1{,}5 \cdot 10^5$ thì mỗi thao tác cỡ $2200 + 14000$ phép, tổng hơn $2 \cdot 10^9$ – quá thời gian; phần đắt nhất chính là 26 phép cho mỗi khối nằm trọn. Bản Python đúng 6/20 test, quá thời gian test 5–11, 13–14, 16–20 (các test đúng chạy lâu nhất 0.338s).
Cách 3Chia căn, gộp nhóm chữ bằng bitmask – O(1) mỗi khối (full)
Đổi góc nhìn: thay vì lưu "chữ gốc $x$ thành chữ gì" ($F[x]$), ta lưu ngược lại: nhom[b][c] = tập các chữ gốc hiện đang mang chữ $c$, dưới dạng bitmask 26 bit. Thao tác đổi $c_1 \to c_2$ trên khối nằm trọn chỉ là gộp nhóm: nhom[c2] |= nhom[c1]; nhom[c1] = 0; – $O(1)$!
- Ban đầu mỗi chữ một nhóm riêng:
nhom[b][c] = 1 << c. Các nhóm luôn rời nhau và phủ đủ 26 chữ gốc. day(b)dựng lại bảng $F$ từ các nhóm (26 × 26 phép) rồi áp xuống $B$ ô; mảngbanđánh dấu khối nào có thay đổi để khỏi "trả nợ" vô ích.- Mỗi thao tác giờ tốn khoảng $4B + n/B$ phép, nên chọn $B \approx \sqrt{n/4}$: với $n = 10^6$ là $B = 500$, khoảng $4000$ phép mỗi thao tác, tổng $6 \cdot 10^8$ phép rất đơn giản.
Kết quả chạy thật: Bản C++ đúng 20/20 test, chạy lâu nhất 0.799s. Full điểm – chỉ với chia căn, nhờ biến bước "sửa bảng 26 ô" thành "gộp hai bitmask".
Cách 4Cây phân đoạn với lazy là ánh xạ 26 chữ (full)
Cách "chuẩn" hơn: cây phân đoạn trên các vị trí, mỗi nút lưu lz[v] = ánh xạ đang chờ áp cho cả đoạn của nút. Cập nhật đoạn $[i, j]$: nút nằm trọn thì hợp $g$ vào lz (26 phép); nút phủ một phần thì đẩy lz xuống hai con trước rồi đệ quy. Cuối cùng đẩy hết xuống lá; lá $p$ cho chữ lz[lá][s[p]].
ap(v, g):lz[v][x] = g[lz[v][x]]– áplz[v]cũ trước rồi tới $g$ (đúng thứ tự thời gian).- Khi đẩy xuống, ánh xạ của cha xảy ra sau mọi ánh xạ đang chờ ở con, nên
ap(con, lz[cha]). - Vòng
for (v = 1; v < sz; v++) day(v);đi theo thứ tự chỉ số tăng – cha luôn được đẩy trước con. - Mỗi thao tác thăm $O(\log n)$ nút, mỗi nút 26 phép: tổng khoảng $1{,}5 \cdot 10^5 \cdot 40 \cdot 26 \approx 1{,}6 \cdot 10^8$.
Kết quả chạy thật: Bản C++ đúng 20/20 test, chạy lâu nhất 0.828s. Full điểm. Bản Python đúng 4/20 test, quá thời gian test 5–20 (các test đúng chạy lâu nhất 0.055s) – bản Python dùng cây không đệ quy và bytes.translate để hợp ánh xạ cho nhanh, nhưng mỗi lần hợp ánh xạ vẫn là một thao tác trên chuỗi 256 byte, đi qua $2\log n$ nút cho mỗi thao tác – chỉ kịp ở subtask 1.
Một biến thể nữa (bản mình nộp chính thức): đổi vai trò – quét vị trí $p$ từ trái sang phải, dựng cây phân đoạn trên chỉ số thao tác; lá $t$ là $g_t$ nếu thao tác $t$ đang phủ $p$, ngược lại là hàm đồng nhất; gốc là hợp mọi thao tác phủ $p$ theo thứ tự thời gian. Thao tác $t$ được "bật" khi $p = i_t$ và "tắt" khi $p = j_t + 1$, nên tổng chỉ có $2m$ lần cập nhật điểm, $O(n + 26 m \log m)$.
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) | Điểm theo subtask |
|---|---|---|---|---|
| 1. Làm đúng như đề | C++ | 8/20 | 0.607s | 20% |
| Python | 6/20 | 0.168s | 20% | |
| 2. Chia căn, mỗi khối một ánh xạ 26 chữ | C++ | 10/20 | 0.266s | 40% |
| Python | 6/20 | 0.338s | 20% | |
| 3. Chia căn, gộp nhóm chữ bằng bitmask – O(1) mỗi khối | C++ | 20/20 | 0.799s | 100% |
| 4. Cây phân đoạn, lazy là ánh xạ 26 chữ | C++ | 20/20 | 0.828s | 100% |
| Python | 4/20 | 0.055s | 20% |