**PHÁT BIỂU LẠI BÀI TOÁN**
Cho đoạn dài $n$ và $q$ đoạn con $\[l_i, r_i\]$ chi phí $c_i$. Phủ kín đoạn dài $n$ bằng các đoạn con sao cho tổng chi phí là nhỏ nhất.
Một hướng giải là DP kết hợp [Segment Tree](https://wiki.vnoi.info/algo/data-structures/segment-tree-extend) quản lí mảng DP. Mình xin giới thiệu một hướng giải khác, đó là đưa về bài toán tìm đường đi ngắn nhất.
**HƯỚNG ĐI**
Dễ thấy để phủ kín đoạn dài $n$ thì sau khi phủ một đoạn con $\[l_i, r_i\]$ với chi phí $c_i$, ta phải chọn đoạn con tiếp theo có đầu trái trong khoảng $\[l_i+1, r_i+1\]$ và tiếp tục như vậy đến $n$.
Nói cách khác, mỗi đoạn con $\[l_i, r_i\]$ là một "cạnh" từ $l_i$ đến phân đoạn $\[l_i+1, r_i+1\]$ với trọng số $c_i$. Từ các cạnh đó, ta tìm đường đi ngắn nhất từ $1$ đến $n+1$ (đến được $n+1$ tức là đã phủ kín từ $1$ đến $n$).
**ÁP DỤNG SEGMENT TREE**
Mấu chốt của cách giải là "thêm cạnh" từ $l_i$ đến phân đoạn $\[l_i+1, r_i+1\]$. Đây chính là lúc dùng Segment Tree chia phân đoạn đó thành $O(\log n)$ nút do cây quản lí và thêm cạnh từ nút $\[l_i, l_i\]$ đến các nút đó. (Segment Tree đang hoạt động như một đồ thị.)
Ban đầu ta khởi tạo Segment Tree có hướng *từ cha* xuống con, vì hiển nhiên khi đến được nút $\[L, R\]$ thì cũng đến được mọi nút con cháu của nó. Sau khi thêm đủ $q$ cạnh, ta thực hiện [Dijkstra](https://viblo.asia/p/thuat-toan-dijkstra-va-ung-dung-aWj53zgQl6m) từ nút $\[1, 1\]$ và lấy kết quả ở nút $\[n+1, n+1\]$.
Để phù hợp với giới hạn thời gian 200 ms và vì các thao tác cập nhật hoàn toàn cho phép, ta cài đặt [Iterative Segment Tree](https://wiki.vnoi.info/translate/codeforces/Efficient-and-easy-segment-trees.md) bằng vòng lặp thay vì gọi đệ quy. Mình để code mẫu C++ cho Iterative Segment Tree và một số chú thích ở bên dưới.
**CODE MẪU**
```cpp
struct SegmentTree
{
int N = 1; //Độ dài mảng cần quản lí
//Các nút lá có id từ N đến 2N-1
//Nút lá u quản lí vị trí u-N+1
//Các nút phân đoạn còn lại có id từ 1 đến N-1
//Nút u khác lá có hai con trái và phải là 2u và 2u+1 như bình thường
void init(int n) //Khởi tạo Segment Tree.
{
while(N <= n) N <<= 1; //Chọn N là lũy thừa 2 để tiện cài đặt
for(int u = N-1; u; --u)
{
g[u].push_back({(u<<1), 0LL}); //Thêm cạnh từ u xuống 2u
g[u].push_back({(u<<1|1), 0LL}); //Thêm cạnh từ u xuống 2u+1
}
}
void update(int u, int l, int r, long long w)
//Thêm cạnh từ u đến [l, r] với trọng số w
{
for(u+=(N-1), l+=(N-1), r+=(N-1); l <= r; l>>=1, r>>=1)
//Tịnh tiến u, l và r thành id các nút lá tương ứng và duyệt từ lá lên gốc
{
if(l&1) g[u].push_back({l++, w});
//Nếu l là con phải thì "anh em" trái của nó không cần thêm cạnh
//Ta thêm cạnh tới l và lùi vào giữa
//Nếu l là con trái thì anh em phải của nó cũng cần thêm cạnh
//Ta duyệt lên cha (hoặc xa hơn) để gom cả hai thành một phân đoạn lớn
//rồi mới thêm cạnh
if(!(r&1)) g[u].push_back({r--, w});
//Tương tự với r
}
}
};
```
sasaki2c
Created at
2 likes