Tài liệu học tập

Bài gợi ý: Tìm dãy con có tổng lớn nhất 2
Tóm tắt: Bạn có một dãy gồm \(N\) số nguyên. Bạn cần xử lý hai loại thao tác: thay đổi giá trị một phần tử, hoặc tìm tổng đoạn con liên tiếp lớn nhất thuộc đoạn từ \(l\) đến \(r\).

Xét dãy 5 phần tử ban đầu 1 2 -3 4 5. Với truy vấn trên đoạn từ \(1\) đến \(3\), đoạn con [1, 2] cho tổng lớn nhất bằng \(3\). Sau đó, nếu cập nhật phần tử đầu thành \(-100\), đoạn \([1, 3]\) trở thành -100 2 -3. Khi đó, kết quả tốt nhất trên đoạn này chỉ còn là \(2\).

Nếu mỗi lần truy vấn ta duyệt lại toàn bộ đoạn \([l, r]\), mỗi thao tác mất tới \(O(N)\) bước. Với \(N \le 5 \cdot 10^4\) và \(M \le 5 \cdot 10^4\), tổng số thao tác có thể lên tới \(2.5 \cdot 10^9\) phép tính. Cách làm này sẽ vượt quá thời gian cho phép.

Giả sử ta chia một đoạn thành hai nửa trái và phải. Đoạn con có tổng lớn nhất chỉ có thể rơi vào ba trường hợp: nằm gọn ở nửa trái, nằm gọn ở nửa phải, hoặc băng qua ranh giới giữa hai nửa. Muốn tính trường hợp băng qua ranh giới, ta cần lấy hậu tố lớn nhất của nửa trái cộng với tiền tố lớn nhất của nửa phải.

Cây phân đoạn (Segment Tree) giúp ta duy trì phép gộp này rất hiệu quả. Mỗi nút của cây quản lý một đoạn và lưu 4 giá trị: tổng cả đoạn sum, tiền tố lớn nhất pref, hậu tố lớn nhất suff, và đoạn con lớn nhất ans. Khi gộp nút con trái và nút con phải, ta cập nhật:
\(ans = \max(\{left.ans, right.ans, left.suff + right.pref\})\),
\(pref = \max(left.pref, left.sum + right.pref)\),
\(suff = \max(right.suff, right.sum + left.suff)\),
cùng với tổng cả đoạn \(sum = left.sum + right.sum\).

Khi cài đặt, bạn có thể kiểm tra từng phần:

• Nút lá tại vị trí \(x\) khởi tạo cả bốn giá trị sum, pref, suff, ans đều bằng giá trị tại vị trí đó.
• Hàm update(id, l, r, pos, val) đi xuống đúng lá pos, thay đổi giá trị rồi gộp ngược lên gốc.
• Hàm query(id, l, r, u, v) trả về một nút chứa đủ 4 thông tin của phần giao giữa đoạn truy vấn và đoạn của nút.

Bài tập tương tự:

• CSES - Subarray Sum Queries | Truy vấn tổng đoạn con: Luyện tập thao tác cập nhật điểm và lấy kết quả lớn nhất trên toàn dãy.
• Đoạn con có tổng lớn nhất: Luyện kỹ năng viết hàm truy vấn đoạn con trên cây phân đoạn mà không có thao tác cập nhật.

Bạn chỉ cần dựng hàm gộp hai nút merge(left, right), gọi update(1, 1, n, x, y) cho thao tác loại 1, và in ra trường ans của nút kết quả từ query(1, 1, n, l, r) cho thao tác loại 2.

Kỳ thi: Orange Contest #02
Tóm tắt: Kỳ thi gồm 5 bài toán với cấu trúc điểm trải rộng từ các bài toán tính toán cơ bản đến xử lý trường hợp, mô phỏng tham lam và quy hoạch động trên tập ước số.

Orange Contest #02 - Phát Triển Dự Án AI yêu cầu tìm số giờ tối thiểu để viết xong \(n\) dòng mã khi người thứ hai có thể chọn tự viết ngay hoặc mất \(z\) giờ chuẩn bị AI rồi tăng tốc gấp 10 lần. Người đọc chỉ cần tính riêng số giờ trọn vẹn theo từng lựa chọn dựa trên phép chia làm tròn lên và lấy giá trị nhỏ hơn.

Orange Contest #02 - Hàng Hóa Trên Kệ kiểm tra khả năng gom các loại hàng hóa giống nhau về cùng các đoạn liền kề sau tối đa một lần hoán đổi hai vị trí trên kệ. Ta quan sát rằng một lần đổi vị trí chỉ tách hoặc gộp tối đa một số ít đoạn, nên sau khi nén giá trị và đếm số khối, chỉ cần kiểm tra các vị trí đầu mút của những phần tử xuất hiện ở nhiều hơn một khối.

Orange Contest #02 - Lối Thoát Không Gian đặt bài toán tìm đường đi ngắn nhất giữa hai trạm \(a\) và \(b\) trong đồ thị đầy đủ với trọng số cạnh là \(\frac{\max(u, v)}{\gcd(u, v)}\). Vì giới hạn đỉnh lên tới \(10^9\) nhưng chi phí phụ thuộc trực tiếp vào quan hệ chia hết, ta có thể rút gọn với \(\gcd(a, b)\) rồi áp dụng quy hoạch động ghi nhớ trên tập các ước số của \(a\) và \(b\).

Orange Contest #02 - Sắp Xếp Chỗ Ngồi yêu cầu tối đa hóa số người được xếp vào các bàn tiệc theo thứ tự đến, trong đó khách hướng nội chỉ ngồi bàn trống, khách hướng ngoại chỉ ngồi bàn đã có người, còn khách hướng trung có thể chọn một trong hai. Do tính chất linh hoạt của khách hướng trung, ta có thể duyệt qua số lượng khách hướng trung đóng vai trò mở bàn mới rồi mô phỏng lại cách xếp theo từng bước.

Orange Contest #02 - Làm Phẳng Kem yêu cầu tìm chiều cao tối đa để san phẳng lớp kem cho từng tiền tố độ dài \(i\) khi phần kem thừa luôn bị gạt sang vị trí bên phải. Thay vì thử từng độ cao cắt dao, ta nhận xét lượng kem dồn lại trên mỗi tiền tố bị chặn trên bởi trung bình cộng tích lũy và chỉ cần duy trì giá trị nhỏ nhất của các mức trung bình này theo từng bước duyệt mảng.

Bạn nên bắt đầu luyện tập với Phát Triển Dự Án AI và Làm Phẳng Kem để làm quen với thao tác tính toán mảng trước khi thử sức với Sắp Xếp Chỗ Ngồi, Hàng Hóa Trên Kệ và Lối Thoát Không Gian.

Bài gợi ý: Không gian phân mảnh
Tóm tắt: Cho một cây gồm \(N\) đỉnh, mỗi đỉnh mang một giá trị nguyên. Ta cần xử lý \(Q\) thao tác gồm thay đổi giá trị tại một đỉnh và tìm đoạn con liên tiếp có tổng lớn nhất trên đường đi giữa hai đỉnh bất kỳ.

Xét đường đi từ đỉnh \(3\) sang đỉnh \(4\) qua đỉnh \(2\). Dãy giá trị tương ứng của các đỉnh trên đường đi này là \(3, -2, 4\). Đoạn con liên tiếp cho tổng lớn nhất là lấy cả dãy với tổng \(3 + (-2) + 4 = 5\). Nếu một đường đi chỉ toàn số âm, đáp số yêu cầu trả về \(0\).

Nếu mỗi lần truy vấn ta lại dùng duyệt theo chiều sâu (DFS) để tìm đường đi và tính tổng đoạn con, chương trình sẽ mất khoảng \(O(N)\) cho mỗi câu hỏi. Với \(N, Q \le 10^5\), tổng số thao tác có thể lên tới \(10^{10}\), gây quá thời gian cho phép.

Ta đang gặp lại bài toán tìm đoạn con có tổng lớn nhất quen thuộc trên mảng một chiều. Để gộp nhanh hai nửa \(L\) và \(R\) của một đoạn, mỗi nút cần lưu bốn thông tin: tổng cả đoạn \(sum\), tiền tố lớn nhất \(pref\), hậu tố lớn nhất \(suff\), và đoạn con lớn nhất \(max\_sub\). Khi nối \(L\) sang trái \(R\), ta có công thức:
\(max\_sub = \max(\{L.max\_sub, R.max\_sub, L.suff + R.pref\})\).
Công thức này xét ba khả năng: đoạn tốt nhất nằm trọn ở nửa trái, nằm trọn ở nửa phải, hoặc băng qua điểm nối giữa hai nửa.

Làm sao mang cấu trúc này lên cây khi đường đi qua nhiều nhánh khác nhau? Ta dùng kỹ thuật phân tách cây thành chuỗi nặng - nhẹ (Heavy-Light Decomposition, hay HLD). Kỹ thuật này trải toàn bộ cây thành các đoạn xích thẳng liên tiếp trên mảng, giúp ta quản lý toàn bộ cây bằng một cây phân đoạn (Segment Tree).

Khi xử lý truy vấn giữa \(u\) và \(v\), ta nhảy từng đoạn xích từ \(u\) và \(v\) lên tổ tiên chung gần nhất. Mỗi bước nhảy trên chuỗi nặng, ta truy vấn trên Segment Tree để lấy kết quả của đoạn đó. Vì đường đi có hướng từ \(u\) lên rồi từ đỉnh chung đi xuống \(v\), ta gom riêng hai nửa đường đi rồi gộp lại ở bước cuối cùng.

Checklist cài đặt:

• Dùng một hàm DFS để tính kích thước cây con và tìm cạnh nặng cho mỗi nút.
• Đánh số lại các đỉnh theo thứ tự đi qua các chuỗi nặng để dựng Segment Tree.
• Viết hàm merge(L, R) để gộp hai đoạn thông tin theo đúng thứ tự trái sang phải.
• Khi truy vấn từ \(u\) và \(v\), gom kết quả nhánh bên \(u\) và nhánh bên \(v\), đảo ngược thông tin nhánh \(u\) trước khi merge với nhánh \(v\), rồi lấy \(\max(ans.max\_sub, 0)\).

Bài tập tương tự:

• CSES - Subarray Sum Queries | Truy vấn tổng đoạn con: Luyện tập thao tác lưu và gộp 4 giá trị của đoạn con lớn nhất trên mảng một chiều.
• Đoạn con có tổng lớn nhất: Làm quen với Segment Tree xử lý truy vấn đoạn con lớn nhất không cập nhật trước khi nâng cấp lên cây.

Bạn hãy bắt đầu bằng việc viết hàm update(1, 1, n, pos[u], x) để thay đổi giá trị của đỉnh trên Segment Tree, sau đó hoàn thiện vòng lặp nhảy chuỗi while (head[u] != head[v]) cho truy vấn đường đi.

Bài gợi ý: Tìm tập độc lập cực đại trên cây — TMAXSET
Tóm tắt: Cho một cây có trọng số tại mỗi đỉnh và nhiều truy vấn. Mỗi truy vấn đưa ra một tập đỉnh con \(Q\), yêu cầu chọn các đỉnh thuộc \(Q\) sao cho không có hai đỉnh nào nối trực tiếp với nhau trên cây và tổng trọng số đạt lớn nhất.

Xét ví dụ với \(3\) đỉnh \(0, 1, 2\) có trọng số lần lượt là \(5, 4, 10\) cùng hai cạnh nối \((0, 2)\) và \((2, 1)\). Với truy vấn \(Q = \{1, 2\}\), hai đỉnh này kề nhau nên ta chỉ được chọn nhiều nhất một đỉnh. Lựa chọn tối ưu là lấy đỉnh \(2\) để đạt tổng trọng số là \(10\).

Thử mọi cách chọn đỉnh trong \(Q\) sẽ mất nhiều thời gian khi số đỉnh lên tới \(200\). Tuy nhiên, cấu trúc cây cho phép ta chia bài toán lớn thành các bài toán nhỏ hơn trên từng nhánh cây con. Ở mỗi đỉnh \(u\), ta chỉ cần quyết định chọn đỉnh \(u\) vào tập hay bỏ qua đỉnh \(u\).

Để giải quyết bài toán, ta dùng phương pháp quy hoạch động trên cây (DP trên cây), tức là lưu lại kết quả tối ưu tại từng cây con để dùng lại. Khi áp dụng duyệt theo chiều sâu (DFS — cách đi dọc theo từng nhánh con xuống đáy rồi mới quay lui), ta duy trì hai giá trị: \(dp[u][1]\) là tổng lớn nhất trong cây con gốc \(u\) khi đỉnh \(u\) được chọn, và \(dp[u][0]\) là tổng lớn nhất khi đỉnh \(u\) không được chọn.

Nếu chọn đỉnh \(u\), mọi nút con \(v\) nối với \(u\) đều không được chọn, nên ta cộng thêm \(dp[v][0]\). Nếu không chọn đỉnh \(u\), nút con \(v\) có thể chọn hoặc không, ta cộng thêm \(\max(dp[v][0], dp[v][1])\). Khi cài đặt, với mỗi truy vấn, ta đánh dấu các đỉnh trong \(Q\) bằng mảng in_Q, gọi dfs(root) để tính bảng phương án, rồi in ra \(\max(dp[root][0], dp[root][1])\).