Chào mọi người.
Chia căn (Sqrt Decomposition) là một kĩ thuật khá phổ biến trong lập trình thi đấu, và tính áp dụng của nó vô cùng cao.
VNOI đã có 2 bài viết về chia căn, tuy nhiên mình thấy phần bài tập áp dụng thì còn hơi ít. Vì vậy hôm nay mình viết bài này để cung cấp một số bài tập khá hay ho & cơ bản dành cho các bạn mới bắt đầu về kĩ thuật này.
Do đây là lần đầu mình viết blog, nên mong mọi người góp ý thêm ở dưới phần bình luận. Cảm ơn mọi người rất nhiều!
Lưu ý: Một số bài trong phần này có thể giải bằng các cấu trúc dữ liệu cao cấp hơn, tuy nhiên do mình còn gà và những cấu trúc dữ liệu đấy cũng không phải là mục đích của mình khi viết bài này, nên các bạn có thể tự tìm hiểu
Cập nhật điểm & Truy vấn
Tóm tắt đề
Có ~n~ cái lỗ nằm dọc theo một đường thẳng được đánh số ~1, 2, ..., n~ từ trái qua phải.
Trong lỗ thứ ~i~ có đặt một lò xo có độ đàn hồi ~a_i~.
Nếu như có một viên bi rơi vào lỗ ~i~ thì nó sẽ nảy lên và rơi vào lỗ ~i + a_i~ nếu như ~i + a_i~ ~<=~ ~n~ còn nếu không sẽ ra khỏi hàng (nhảy vượt qua lỗ ~n~), quá trình này lại tiếp tục như vậy... cho đến khi viên bi nhảy vượt qua lỗ ~n~.
Có ~m~ thao tác được người chơi bi thực hiện lần lượt thuộc một trong hai loại sau:
~0~ ~a~ ~b~: Thay lò xo có độ đàn hồi ~b~ vào lỗ ~a~
~1~ ~b~: Bắn một viên bi vào lỗ ~a~ và đếm xem nó nhảy qua bao nhiêu lỗ trước khi vượt qua lỗ ~n~?
Giải thuật
Chia các viên bi thành các khối, mỗi khối có kích thước ~sqrt(n)~ phần tử
Lưu ý, khi cài đặt, chúng ta thường chia thành các khối có kích thước ~sqrt(MAXN)~, chứ không dùng đúng ~sqrt(n)~, bởi vì chia cho hằng số bao giờ cũng nhanh hơn khi chia cho biến
Gọi ~last_i~ ~=~ vị trí xa nhất khác khối với viên bi thứ ~i~, mà viên bi thứ ~i~ có thể nhảy tới được, và ~cnt_i = ~ số bước con ~i~ cần nhảy để đến được vị trí là ~last_i~
Để xây dựng mảng ~last~ và ~cnt~ ban đầu, ta sẽ xây dựng từ các viên bi thứ ~n~ về thứ nhất
Với mỗi viên bi thứ i, ta sẽ xây dựng ~last_i~ và ~cnt_i~ theo kiểu DP như sau:
Gọi ~nxt~ = vị trí tiếp theo của viên bi thứ ~i~.
- Nếu ~nxt > n~ thì ~last_i = i~ và ~cnt_i = 0~
- Nếu ~nxt~ cùng khối với ~i~, thì ~last_i = last_{nxt}~ và ~cnt_i = cnt_{nxt} + 1~
- Nếu ~nxt~ khác khối với ~i~, thì ~last_i = nxt~ và ~cnt_i = 1~
Khi đó, ta sẽ xử lý các truy vấn như sau:
Với truy vấn ~1~, ta sẽ nhảy dần từ ~x~ -> ~last_x~ cho đến khi nào ~x~ không thể nhảy sang block khác được nữa, nghĩa là ~last_x == x~. Sau đó, ta sẽ nhảy ~a_x~ bước cho đến khi vượt quá n.
Độ phức tạp cho truy vấn này là ~sqrt(n)~, do với mỗi bước nhảy từ ~x~ đến ~last_x~, ta đã nhảy qua ~1~ block, tương đương với ~sqrt(n)~ phần tử, và khi không nhảy qua các block được nữa, ta chỉ nhảy đến các ô thuộc cùng 1 block, và mỗi block có số phần tử không quá ~sqrt(n)~
Với truy vấn ~0~, ta nhận thấy: chỉ những vị trí ~i~ nằm ở bên trái hoặc trùng với ~x~, và thuộc cùng block với ~x~ mới bị thay đổi ~last~ và ~cnt~, nên ta chỉ update cho các giá trị ~i~ như thế. Còn phần update, thì nó giống như khi ta dựng mảng ban đầu. Độ phức tạp cho phần này là ~sqrt(n)~
Code
CSES 1648 - Dynamic Range Sum Queries
Tóm tắt đề
Cho 1 mảng ~n~ phần tử, xử lí ~q~ truy vấn:
- ~1~ ~k~ ~u~: gán ~a_k~ ~=~ ~u~
- ~2~ ~a~ ~b~: tính tổng đoạn ~[a, b]~
Giải thuật
Chia mảng thành các block có ~sqrt(n)~ phần tử
Gọi ~s_i~ = tổng các phần tử thuộc block thứ ~i~
Với truy vấn ~1~, gọi ~idx~ là block chứa phần tử thứ ~k~, và ~dif~ ~=~ ~u~ ~-~ ~a_k~
Cập nhật: ~s_{idx} += dif~ và gán ~a_k~ = ~u~
Với truy vấn ~2~
Nếu ~a~ và ~b~ thuộc cùng 1 khối, thì ta chỉ cần for trâu để tính tổng trong đoạn này, độ phức tạp sẽ là ~sqrt(n)~
Ngược lại, gọi ~L~ = block chứa ~a~, ~R~ = block chứa ~b~. Kết quả sẽ là tổng các ~s_i~ trong khoảng ~[L + 1, R - 1]~ và tổng các ~a_i~ trong khoảng [~a~, cuối block ~L~] và [đầu block ~R~, ~b~]
Code
Áp dụng
CSES 1749 - List Removals - chỉ phù hợp để cài cho biết thuật, thực tế thuật ~O(sqrt(n) * log(n) * q)~ hoàn toàn không thể giải được bài này
Cập nhật đoạn & Truy vấn
Tóm tắt đề
Cho 1 mảng ~n~ phần tử, xử lí ~q~ truy vấn:
- ~1~ ~a~ ~b~ ~x~: tăng mỗi phần tử từ vị trí ~a~ đến vị trí ~b~ ~x~ đơn vị
- ~2~ ~a~ ~b~: tính tổng đoạn ~[a, b]~
Giải thuật
Chia mảng thành các block có ~sqrt(n)~ phần tử
Gọi ~s_i~ = tổng các phần tử trong block i, ~add_i~ = tổng các giá trị được thêm vào một trong các phần tử của block ~i~
Với truy vấn ~2~, ta xét các trường hợp sau:
- Nếu ~a~ và ~b~ thuộc cùng một block, gọi ~id~ = block chứa ~a~, đơn giản ta for từ ~a~ đến ~b~ và tính tổng của các ~a_i~ ~+~ ~add_{id}~
- Ngược lại, gọi ~L~ = block chứa ~a~, ~R~ = block chứa ~b~, kết quả sẽ là tổng các ~s_i~ ~+~ (~add_i~ * kích thước của block) với ~i~ thuộc ~[L + 1, R - 1]~, cộng với tổng các ~a_i~ ~+~ ~add_L~ với ~i~ thuộc [~a~, cuối block ~L~], cộng với tổng các ~a_i~ ~+~ ~add_R~ với ~i~ thuộc [đầu block ~R~, ~b~]
Với truy vấn 1, ta cần cập nhật như sau
Gọi hàm ~manualUpdate(id, l, r, value)~ là dùng để update cho khoảng ~[l, r]~, tăng lên 1 giá trị là ~value~, khối chứa bọn này là ~id~
Hàm này sẽ thực hiện như sau:
- Đầu tiên, ta cần phải cập nhật hết tất cả bọn đang nằm ở ~s_i~ vào các phần tử trong khối này trước, bằng cách cộng tất cả các con thuộc khối thứ ~id~ 1 lượng là ~add_{id}~
- Sau đó, tiến hành cập nhật trâu tăng tất cả phần tử trong khoảng ~[l, r]~ một lượng là ~value~
- Cuối cùng, dựng lại ~s_{id}~ và gán ~add_{id}~ ~=~ ~0~
Gọi hàm ~blockUpdate(l, r, value)~ là dùng để update tăng các khối có chỉ số thuộc khoảng ~[l, r]~ một lượng là ~value~
Sau đó, với mỗi truy vấn cập nhật, nếu ~a~ và ~b~ cùng khối, ta gọi ~manualUpdate(a, b, x)~, ngược lại, ta cập nhật như sau:
manualUpdate(a, cuối block chứa a, x);
blockUpdate(block chứa a + 1, block chứa b - 1, x);
manualUpdate(đầu block chứa b, b, x);
Code
Tóm tắt đề
Cho một mảng ~n~ số, ban đầu tất cả các phần tử có giá trị bằng ~0~. Xử lí ~m~ truy vấn:
- ~0~ ~s~ ~e~: đảo trạng thái các bit của các phần tử có chỉ số thuộc ~[s, e]~
- ~1~ ~s~ ~e~: tính tổng các phần tử có chỉ số thuộc ~[s, e]~
Giải thuật
Tương tự bài trên, tuy nhiên ta gọi ~flip_i~ = block thứ ~i~ đã bị đảo chẵn hay lẻ lần, và việc xử lí ở hàm ~manualUpdate~ phải thay đổi một chút vì nếu block thứ ~i~ đã bị đảo chẵn lần, thì trạng thái của nó vẫn giữ nguyên.
Code
Áp dụng
Mo's Algorithm
Chi tiết tại bài viết của VNOI
Tóm tắt đề
Cho mảng ~n~ số. Gọi ~power~ của một đoạn con ~[l, r]~ là tổng các giá trị ~K_s~ ~*~ ~K_s~ ~*~ ~s~ với mọi số ~s~ phân biệt trong đoạn, và ~K_s~ ~=~ số lượng số ~s~ trong đoạn.
Cho ~q~ truy vấn, mỗi truy vấn yêu cầu tính ~power~ của đoạn ~[l, r]~
Giải thuật
Sort các truy vấn theo thuật toán Mo
Đặt ~cur_l~ ~=~ ~1~, ~cur_r~ ~=~ ~0~
Với mỗi truy vấn ~[l, r]~, ta sẽ đẩy con trỏ ~cur_l~ và ~cur_r~ cho đến khi chạm được vào ~2~ đầu mút của truy vấn này
Đặt ~ans~ = kết quả của bài toán hiện tại, ~cnt_x~ = số lần xuất hiện của số ~x~, ta sẽ thêm và xoá một số như sau
- Thêm 1 số ~x~: ~ans~ ~+=~ ~x~ ~*~ ~2~ ~*~ ~x~ ~+~ ~1~, ~cnt_{x}++~
- Xoá 1 số ~x~: ~ans~ ~+=~ ~x~ ~*~ ~-2~ ~*~ ~x~ ~+~ ~1~, ~cnt_{x}--~
Cụ thể chứng minh công thức này mình xin phép nhường lại cho bạn đọc.
Code
Áp dụng
Chia căn truy vấn (Batching)
Các bạn có thể tham khảo tại USACO
Tóm tắt đề
Cho cây ~n~ đỉnh, ban đầu các đỉnh được tô màu xanh trừ đỉnh ~1~ được tô màu đỏ. Có ~q~ truy vấn:
- ~1~ ~v~: Tô đỉnh ~v~ thành màu đỏ.
- ~2~ ~v~: Tìm đường đi ngắn nhất từ đỉnh ~v~ đến một đỉnh đỏ bất kì.
Giải thuật
Nhận thấy:
- Nếu số lượng truy vấn là đủ nhỏ, ta có thể chuẩn bị trước một mảng ~dist_u~ = đường đi ngắn nhất từ một trong các đỉnh màu đỏ đến đỉnh ~u~. Việc này có thể thực hiện trong ~O(n)~ bằng BFS multisource.
- Khoảng cách giữa 2 đỉnh bất kì trên cây có thể tính trong ~O(1)~ bằng LCA.
- Từ đó ta có thuật toán nếu ~q~ nhỏ: tính mảng ~dist~, sau đó với mỗi truy vấn, gán kết quả bằng ~dist_v~, sau đó for mọi đỉnh ~u~ trong các truy vấn trước đó và cập nhật lại kết quả
Với ~q~ lớn, ta sẽ chia các truy vấn thành các khối có ~sqrt(n)~ phần tử
Sau đó, với mỗi khối, ta xử lí y như trường hợp ~q~ nhỏ ở trên. Lưu ý: bởi vì sau khi kết thúc mỗi khối ta đều BFS lại, nên việc for lại các đỉnh ~u~ trong các truy vấn trước ta chỉ for đến các truy vấn thuộc cùng block với truy vấn đang xét hiện tại.
Như vậy độ phức tạp cho bài này là ~O(n * sqrt(n))~
Code
Áp dụng:
Một số bài toán khác
Tóm tắt đề
Cho mảng ~n~ số có giá trị ~<=~ ~c~.
Cho ~m~ truy vấn, mỗi truy vấn ~[l, r]~ yêu cầu kiểm tra xem trong đoạn này có phần tử nào xuất hiện nhiều hơn ~(r - l + 1) / 2~ lần không. Nếu có, in phần tử đó ra
Giải thuật
Nếu truy vấn có độ dài ~<=~ ~2*sqrt(n)~, ta duyệt trâu để kiểm tra
Ngược lại, đáp án của chúng ta bắt buộc phải là số xuất hiện nhiều hơn hoặc bằng ~sqrt(n)~ lần trong dãy ban đầu, ta for hết giá trị như vậy và đếm
Độ phức tạp: ~O(max(n, q) * sqrt(n))~
Áp dụng: Free Contest 100 - GOODARR (subtask ~3~)
Tóm tắt đề
Cho cây ~n~ đỉnh, mỗi đỉnh có giá trị ~<=~ ~c~.
Cho ~q~ truy vấn dạng ~x~ ~y~, ta cần tính khoảng cách ngắn nhất từ các đỉnh có giá trị ~y~ đến đỉnh ~x~.
Giải thuật
Chia các đỉnh thành ~2~ loại, loại ~1~ là giá trị của nó có số lần xuất hiện ~<= sqrt(n)~, và ngược lại.
Tính trước mảng ~dist(x, y)~ = khoảng cách từ đỉnh ~x~ đến đỉnh thứ ~y~ của loại ~2~.
Với mỗi truy vấn, nếu ~y~ là màu loại 1, ta duyệt hết các đỉnh có màu ~y~ để tính, có không quá ~sqrt(n)~ đỉnh như vậy.
Ngược lại, ta sử dụng mảng ~dist(x, y)~ để trả lời.
Áp dụng: Milk Visits
Tham khảo thêm
Tổng kết
Do đây là lần đầu mình viết blog, nên còn có thể có sai sót nhiều. Mọi người ai có góp ý, sửa đổi gì xin bình luận ở bên dưới để mình cải thiện, rút kinh nghiệm cho lần sau (hoặc không có lần sau). Cảm ơn các bạn!
Vì mình khá lười nên số lượng bài tập cho phần này vẫn còn khá ít, ai có bài gì hay xin bình luận bên dưới ạ.
Bình luận
cảm ơn anh, bài viết rất là hay ạ :3
mình cảm ơn
.