Bỏ qua để đến nội dung

Chia căn và thuật toán Mo

Mức độ: Chuyên sâu

Một mảng n số, q câu hỏi trên đoạn [l, r] xen kẽ với các lần sửa mảng. Duyệt cả đoạn mỗi câu hỏi mất tới n bước, cả bài n × q bước. Cây phân đoạn làm mỗi câu hỏi trong log n bước nhưng chỉ dùng được khi thông tin của hai nửa ghép được với nhau. Chia căn chậm hơn một chút (khoảng n\sqrt{n} bước mỗi câu hỏi) nhưng dễ viết và dùng được cho nhiều câu hỏi mà cây phân đoạn khó làm.

Chia mảng thành các khối liên tiếp, mỗi khối B phần tử (khối cuối có thể ngắn hơn). Phần tử ở vị trí i (đánh số từ 0) thuộc khối i ÷ B. Với mỗi khối, tính sẵn thông tin cần hỏi, ví dụ tổng các phần tử trong khối.

Mảng 3 1 4 1 5 9 2 6 5 (n = 9, B = 3):

Khối012
Phần tử3 1 41 5 92 6 5
Tổng khối81513

Hỏi tổng đoạn từ vị trí 1 đến 7 (đánh số từ 0): đoạn gồm phần lẻ đầu là vị trí 1, 2 của khối 0 (cộng từng số: 1 + 4), khối trọn vẹn 1 (lấy tổng khối: 15), và phần lẻ cuối là vị trí 6, 7 của khối 2 (2 + 6). Tổng là 5 + 15 + 8 = 28.

Số bước: hai phần lẻ có không quá 2B phần tử, số khối trọn vẹn không quá n ÷ B. Tổng là 2B + n ÷ B, nhỏ nhất khi B khoảng n\sqrt{n}, lúc đó mỗi câu hỏi khoảng 3n\sqrt{n} bước. Với n = 105 là khoảng 1000 bước, so với 105 bước nếu duyệt cả đoạn.

Sửa ai thành v: cập nhật tổng của khối chứa i (cộng thêm v - ai), chỉ một bước.

import sys
from math import isqrt
def tao_khoi(a):
"""Kích thước khối B và tổng từng khối."""
B = isqrt(len(a)) + 1
tong_khoi = [0] * (len(a) // B + 1)
for i, x in enumerate(a):
tong_khoi[i // B] += x
return B, tong_khoi
def tong_doan(a, B, tong_khoi, l, r):
"""Tổng a[l..r] (đánh số từ 0)."""
tong = 0
while l <= r and l % B != 0: # phần lẻ đầu
tong += a[l]
l += 1
while l + B - 1 <= r: # các khối trọn vẹn
tong += tong_khoi[l // B]
l += B
while l <= r: # phần lẻ cuối
tong += a[l]
l += 1
return tong
def sua(a, B, tong_khoi, i, v):
tong_khoi[i // B] += v - a[i]
a[i] = v

Muốn cộng v vào cả đoạn, mỗi khối giữ thêm một số cho_ca_khoi: khối trọn vẹn chỉ cần cộng v vào số đó (một bước), phần lẻ thì cộng trực tiếp vào từng phần tử. Đây là cùng ý với cập nhật lười của cây phân đoạn.

Sức mạnh của chia căn là mỗi khối giữ được bất cứ thông tin gì tính lại được trong khoảng B bước. Ví dụ giữ bản sắp xếp của từng khối thì đếm được số phần tử nhỏ hơn x trong đoạn: khối trọn vẹn dùng tìm kiếm nhị phân, phần lẻ đếm từng số (bài 4).

Nhiều câu hỏi rất khó ghép từ hai nửa, ví dụ trên đoạn [l, r] có bao nhiêu giá trị khác nhau. Nhưng nếu đã biết câu trả lời cho [l, r] thì câu trả lời cho [l, r + 1] tính rất nhanh: giữ mảng dem[x] là số lần x xuất hiện trong đoạn; thêm ar + 1 vào, nếu dem của nó từ 0 lên 1 thì có thêm một giá trị mới. Bỏ một phần tử ra cũng tương tự.

Vậy có thể giữ một đoạn [l, r] “đang xét” và dịch hai đầu từng bước tới đoạn của câu hỏi. Vấn đề là thứ tự: nếu các câu hỏi nhảy lung tung, mỗi lần dịch có thể tới n bước. Mo (đặt theo tên người phổ biến cách này) đọc hết các câu hỏi trước rồi sắp xếp lại để tổng số bước dịch nhỏ:

  1. Chia vị trí thành các khối B phần tử, B khoảng n\sqrt{n}.
  2. Sắp xếp câu hỏi theo khối chứa l, cùng khối thì theo r tăng dần.
  3. Trả lời lần lượt theo thứ tự đó, rồi in ra theo thứ tự ban đầu của đề.

Vì sao nhanh? Các câu hỏi cùng khối l có r tăng dần, nên đầu phải chỉ đi sang phải, tối đa n bước cho mỗi khối; có n ÷ B khối, tổng n2 ÷ B bước. Đầu trái mỗi câu hỏi chỉ đi trong một khối (hoặc sang khối kế), khoảng B bước, tổng q × B bước. Với B khoảng n\sqrt{n}, cả bài khoảng (n + q)n\sqrt{n} bước. Với n = q = 105 là khoảng 6 × 107 bước, so với 1010 bước nếu duyệt từng đoạn.

import sys
from math import isqrt
def so_gia_tri_khac_nhau(a, cau_hoi):
"""Trả lời offline: mỗi câu hỏi (l, r), đánh số từ 0, hỏi số giá trị khác nhau trong a[l..r]."""
B = isqrt(len(a)) + 1
thu_tu = sorted(range(len(cau_hoi)), key=lambda k: (cau_hoi[k][0] // B, cau_hoi[k][1]))
dem = [0] * (max(a) + 1)
khac_nhau = 0
l, r = 0, -1 # đoạn đang xét: a[l..r], ban đầu rỗng
tra_loi = [0] * len(cau_hoi)
for k in thu_tu:
ql, qr = cau_hoi[k]
while r < qr: # nới đầu phải
r += 1
dem[a[r]] += 1
if dem[a[r]] == 1:
khac_nhau += 1
while l > ql: # nới đầu trái
l -= 1
dem[a[l]] += 1
if dem[a[l]] == 1:
khac_nhau += 1
while r > qr: # thu đầu phải
dem[a[r]] -= 1
if dem[a[r]] == 0:
khac_nhau -= 1
r -= 1
while l < ql: # thu đầu trái
dem[a[l]] -= 1
if dem[a[l]] == 0:
khac_nhau -= 1
l += 1
tra_loi[k] = khac_nhau
return tra_loi

Nên nới đoạn trước, thu đoạn sau như trong code, để đoạn đang xét không bao giờ bị “âm” (l lớn hơn r + 1).

Mo chỉ dùng được khi:

  • đọc được hết câu hỏi trước khi trả lời (offline) và mảng không bị sửa giữa chừng;
  • thêm hoặc bỏ một phần tử ở hai đầu đoạn cập nhật được câu trả lời nhanh (thường một vài bước).

Mẹo nhỏ: ở các khối thứ tự lẻ, sắp r giảm dần thay vì tăng dần. Đầu phải đi tới cuối khối này rồi quay về ở khối sau thay vì nhảy về đầu, bớt được khoảng một nửa số bước của đầu phải.

Gồm 11 bài, chia thành 3 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Dòng đầu có n, q (1 ≤ n, q ≤ 105), dòng thứ hai có n số nguyên (|ai| ≤ 109). q dòng sau mỗi dòng là 1 i v (gán ai = v, |v| ≤ 109) hoặc 2 l r (hỏi tổng al + … + ar). In ra đáp số các câu hỏi loại 2.

Ví dụ:

NhậpIn ra
5 4
1 2 3 4 5
2 2 4
1 3 10
2 1 5
2 3 3
9
22
10

Kiểm tra: nhập

9 5
3 1 4 1 5 9 2 6 5
2 2 8
1 5 -5
2 4 6
1 9 0
2 1 9
Xem đáp số
28
5
21

Hướng dẫn giải chi tiết: liên hệ tác giả.

Dòng đầu có n, q (1 ≤ n, q ≤ 105), dòng thứ hai có n số nguyên (|ai| ≤ 109). q dòng sau mỗi dòng là 1 l r v (cộng v vào mọi al, …, ar, |v| ≤ 104) hoặc 2 l r (hỏi tổng al + … + ar). In ra đáp số các câu hỏi loại 2.

Ví dụ:

NhậpIn ra
6 4
1 1 1 1 1 1
1 2 5 3
2 1 6
1 4 6 -1
2 5 6
18
3

Kiểm tra: nhập

10 6
5 3 8 1 0 2 7 4 6 9
1 1 10 2
2 3 7
1 2 4 5
2 1 3
1 6 9 -3
2 4 10
Xem đáp số
28
32
36

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Nhỏ nhất trên đoạn có sửa phần tử

Phần tiêu đề “Bài 3. Nhỏ nhất trên đoạn có sửa phần tử”

Dòng đầu có n, q (1 ≤ n, q ≤ 105), dòng thứ hai có n số nguyên (|ai| ≤ 109). q dòng sau mỗi dòng là 1 i v (gán ai = v) hoặc 2 l r (hỏi số nhỏ nhất trong al, …, ar). In ra đáp số các câu hỏi loại 2.

Ví dụ:

NhậpIn ra
6 4
4 2 7 1 8 3
2 1 3
1 4 9
2 3 6
2 4 5
2
3
8

Kiểm tra: nhập

10 6
9 4 6 2 8 5 7 1 3 10
2 2 7
1 4 11
2 2 7
1 8 0
2 5 10
2 9 9
Xem đáp số
2
4
0
3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Đếm số không vượt quá x trong đoạn

Phần tiêu đề “Bài 4. Đếm số không vượt quá x trong đoạn”

Dòng đầu có n, q (1 ≤ n, q ≤ 5 × 104), dòng thứ hai có n số nguyên (|ai| ≤ 109). q dòng sau mỗi dòng là 1 i v (gán ai = v) hoặc 2 l r x (hỏi có bao nhiêu chỉ số i trong [l, r] mà ai ≤ x). In ra đáp số các câu hỏi loại 2.

Ví dụ:

NhậpIn ra
6 3
5 1 4 2 6 3
2 1 6 3
1 2 7
2 2 5 4
3
2

Kiểm tra: nhập

10 5
8 3 5 9 1 4 7 2 6 0
2 1 10 4
2 3 8 6
1 5 10
2 3 8 6
2 4 4 9
Xem đáp số
5
4
3
1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Dòng đầu có n, q (1 ≤ n, q ≤ 105), dòng thứ hai có n số nguyên (1 ≤ ai ≤ 106), q dòng sau mỗi dòng có l, r (1 ≤ l ≤ r ≤ n). Với mỗi câu hỏi, in ra số giá trị khác nhau trong al, …, ar.

Ví dụ:

NhậpIn ra
6 3
1 2 1 3 2 2
1 3
2 6
4 4
2
3
1

Kiểm tra: nhập

10 5
5 5 1 2 5 3 1 2 4 5
1 10
2 4
3 8
5 6
6 10
Xem đáp số
5
3
4
2
5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Dòng đầu có n, q (1 ≤ n, q ≤ 105), dòng thứ hai có n số nguyên (1 ≤ ai ≤ 106), q dòng sau mỗi dòng có l, r. Với mỗi câu hỏi, đếm số cặp chỉ số (i, j) với l ≤ i nhỏ hơn j ≤ r mà ai = aj.

Ví dụ:

NhậpIn ra
6 3
1 2 1 1 2 3
1 4
2 5
1 6
3
2
4

Kiểm tra: nhập

10 5
4 4 4 2 4 2 2 1 4 2
1 10
1 3
4 7
2 9
8 8
Xem đáp số
16
3
3
9
0

Hướng dẫn giải chi tiết: liên hệ tác giả.

Dòng đầu có n, q (1 ≤ n, q ≤ 105), dòng thứ hai có n số nguyên (1 ≤ ai ≤ 106), q dòng sau mỗi dòng có l, r. Sức mạnh của đoạn al, …, ar là tổng của cx × cx × x theo mọi giá trị x, với cx là số lần x xuất hiện trong đoạn. In ra sức mạnh của từng đoạn được hỏi.

Ví dụ:

NhậpIn ra
4 2
1 2 1 1
1 4
2 3
11
3

Kiểm tra: nhập

8 4
3 1 3 3 2 1 2 3
1 8
2 5
4 7
1 1
Xem đáp số
60
15
12
3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Dòng đầu có n, q, k (1 ≤ n, q ≤ 105, 1 ≤ k ≤ n), dòng thứ hai có n số nguyên (1 ≤ ai ≤ 106), q dòng sau mỗi dòng có l, r. Với mỗi câu hỏi, in ra số giá trị xuất hiện đúng k lần trong al, …, ar.

Ví dụ:

NhậpIn ra
7 3 2
1 2 1 3 2 2 3
1 4
1 7
2 6
1
2
0

Kiểm tra: nhập

10 5 3
4 1 4 4 2 1 1 2 4 2
1 10
1 4
2 7
5 10
3 9
Xem đáp số
2
1
1
1
1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Dòng đầu có n, q, k (1 ≤ n, q ≤ 105, 0 ≤ k ≤ 106), dòng thứ hai có n số nguyên (0 ≤ ai ≤ 106), q dòng sau mỗi dòng có l, r. Với mỗi câu hỏi, đếm số cặp (i, j) với l ≤ i ≤ j ≤ r mà ai XOR ai + 1 XOR … XOR aj = k.

Ví dụ:

NhậpIn ra
6 2 3
1 2 1 1 0 3
1 6
3 5
7
0

Kiểm tra: nhập

8 4 1
1 0 1 1 0 0 1 1
1 8
2 5
3 3
4 8
Xem đáp số
18
4
1
8

Hướng dẫn giải chi tiết: liên hệ tác giả.

Có n lỗ xếp thành hàng, đánh số 1 đến n. Lỗ i có sức bật ai ≥ 1: quả bóng rơi vào lỗ i sẽ nảy sang lỗ i + ai, nếu i + ai lớn hơn n thì bóng ra khỏi hàng. Dòng đầu có n, q (1 ≤ n, q ≤ 105), dòng thứ hai có a1, …, an (1 ≤ ai ≤ n). q dòng sau mỗi dòng là 0 i v (đổi ai thành v, 1 ≤ v ≤ n) hoặc 1 i (thả bóng vào lỗ i). Với mỗi lần thả, in ra lỗ cuối cùng bóng chạm trước khi ra khỏi hàng và số lần bóng rơi vào lỗ (tính cả lỗ i).

Ví dụ:

NhậpIn ra
8 5
1 1 1 1 1 2 8 2
1 1
0 1 3
1 1
0 3 4
1 2
8 7
8 5
7 3

Kiểm tra: nhập

10 6
2 3 1 2 4 1 3 2 1 5
1 1
1 4
0 4 6
1 1
0 2 1
1 2
Xem đáp số
10 6
10 4
10 4
10 4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Dòng đầu có n (1 ≤ n ≤ 3 × 104), dòng thứ hai có n số nguyên (|ai| ≤ 109), dòng thứ ba có q (1 ≤ q ≤ 3 × 104), q dòng sau mỗi dòng có x, y (1 ≤ x, y ≤ n). Với mỗi câu hỏi, in ra ax + ax + y + ax + 2y + … (cộng tới khi chỉ số vượt quá n).

Ví dụ:

NhậpIn ra
5
1 2 3 4 5
3
1 2
2 2
3 1
9
6
12

Kiểm tra: nhập

10
3 -1 4 1 -5 9 2 6 5 3
5
1 3
2 3
4 7
1 1
10 2
Xem đáp số
9
0
1
27
3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Th.S Trần Huy Phúc

Th.S Trần Huy Phúc

Principal Software Engineer @Adnovum & Bumbii Academy