Ta sử dụng chia căn và Convex Hull Trick cho bài này.

Để xử lí ~n~ truy vấn, ta chia nó ra ~\beta~ block. Ở đây gán ~\beta = \sqrt n~.

Mỗi block, ta sẽ dựng một bao lồi dựa trên các đường thẳng ở trong block đó. Để tối ưu độ phức tạp, ta dựng bao lồi bằng deque, như vậy cần sắp xếp các đường thẳng dạng ~a\times x + b~ theo thứ tự ~a~ tăng dần.

Giả sử ta đang xét tới các truy vấn trong block ~i~. Đầu tiên ta sẽ xử lí các truy vấn loại ~2~ trước bằng cách đánh dấu các truy vấn bị xóa. Nếu truy vấn bị xóa đó nằm ở block bé hơn ~i~, ta sẽ xây lại bao lồi ở block đó. Việc xây lại này mất độ phức tạp là ~O(\sqrt n)~ với mỗi truy vấn xóa.

Sau đó ta xét các truy vấn loại ~3~, để tận dụng được các tập bao lồi mà ta xây dựng bằng deque ở các block trước, ta cần sắp xếp các truy vấn này theo thứ tự ~q~ tăng dần để truy vấn. Tiếp theo, ta xét các truy vấn có ~q~ tăng từ bé tới lớn và tối ưu kết quả với từng block. Sau đó, ta sẽ xét các đường thẳng trong block hiện tại mà vẫn tồn tại ở thời điểm truy vấn ~q~ đang xét để tối ưu. Cuối cùng, ta đi xét tiếp các đường thẳng bị xóa bởi một truy vấn trong block ~i~, giả sử truy vấn loại ~3~ ta đang xét là truy vấn thứ ~u~, truy vấn xóa của ta là truy vấn ~v~, thì nếu ~v > u~ và ~v_x < u~, nghĩa là ở thời điểm truy vấn ~u~ xảy ra thì đường thẳng ở vị trí ~v_x~ vẫn tồn tại. Vậy nên, ta cần xét thêm các đường thẳng như thế này. Như vậy, độ phức tạp ở đây là ~O(\sqrt n + \sqrt n \times log)~

Đối với các truy vấn loại ~1~, ta sẽ xây bao lồi dựa trên tập các đường thẳng chưa bị xóa trong block ~i~.

Độ phức tạp: ~O(n \times \sqrt n + n \times log)~

Lưu ý, không nhất thiết đặt ~\beta = \sqrt n~, ta có thể đặt nó lớn hơn hoặc bé hơn tùy vào thuật toán cần xử lí, lúc đó có thể chạy tối ưu hơn.