Mình xin đóng góp lời giải của bài này :

Nhận xét :

Tại ngày thứ i, số bông hoa được tạo ra thêm bằng số giao điểm giữa hai cạnh dọc của ngày thứ i (Li, Ri) với các cạnh ngang của các ngày trước đó.

Vì số bông hoa đã được tạo ra rồi sẽ không được tính nữa (nếu tọa độ bông hoa là giao điểm) nên ta chú ý trừ đi cho thích hợp.

Ý tưởng : Với mỗi đoạn Li, Ri ta sẽ phủ được đoạn Li + 1 -> Ri – 1.

(Vì trục của ngày sau luôn lớn hơn ngày trước 1 đơn vị, nên ta chỉ cần quan tâm hoành độ Li và Ri).

Ta dễ thấy rằng số bông hoa mới được tạo ra sẽ là số giao điểm giữa Li, Ri với các cạnh ngang trước đó hay nói cách khác là số lần được phủ (và chưa có hoa) tại hai điểm Li và Ri.

Cách làm :

Gọi f[i] là số lần được phủ tại điểm i ( số cạnh ngang phủ được điểm i).

Mỗi ngày,

• Số bông hoa mới được tạo ra sẽ là f[Li] + f[Ri].

• Ta sẽ cập nhật f[i] bằng cách bỏ đi số bông hoa đã xuất hiện tại Li và Ri <=> f[Li] = f[Ri] = 0; (Xóa hết giao điểm tại Li, Ri)

• Và tăng đoạn Li + 1 -> Ri – 1 lên 1.

Sub 1, 3 : (O(n * R))

Với mỗi Li, Ri

1. Res = f[Li] + f[Ri]

2. F[Li] = F[Ri] = 0;

3. Duyệt : i – (Li + 1 -> Ri – 1), f[i] += 1;

Sub 4 : (O(n * LogR))

Vẫn với ý tưởng trên, ta sẽ giảm chi phí tính cập nhật f[] từ O(R) xuống O(logR).

Để làm được như thế ta sẽ sử dụng CTDL Segment Tree và kĩ thuật Lazy Update.

Bài toán chúng ta trở thành :

Thêm vào tất cả phần tử thuộc đoạn L, R một giá trị Val. Tính giá trị tại vị trí Pos.

Các bạn có thể tham khảo cách làm này tại đây : https://vnoi.info/wiki/algo/data-structures/segment-tree-extend.md#2-lazy-propagation