Cây Li Chao Xóa Động

Buổi 37 — Convex Hull Trick
Points
100
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Bạn cần quản lý một tập hợp động các đường thẳng hỗ trợ cả thao tác thêm và xóa. Xử lý $Q$ truy vấn thuộc ba loại:

  • 1 id a b: Thêm đường thẳng có mã định danh duy nhất id với phương trình $y = ax + b$.
  • 2 id: Xóa đường thẳng có mã id khỏi tập hợp (đảm bảo id đang tồn tại).
  • 3 x: Tìm giá trị nhỏ nhất của $ax + b$ tại hoành độ $x$ trong số các đường thẳng đang có mặt. Nếu tập hợp rỗng, in ra NO.
Dữ liệu vào
  • Dòng đầu chứa số nguyên $Q$ ($1 \le Q \le 10^5$).
  • $Q$ dòng tiếp theo, mỗi dòng mô tả một truy vấn thuộc một trong ba loại trên ($1 \le \text{id} \le 10^9$).
Dữ liệu ra
  • Với mỗi truy vấn loại 3, in ra kết quả hoặc NO trên một dòng.
Ví dụ
Input Output
7
1 10 2 1
1 20 -1 10
3 5
2 20
3 5
2 10
3 5
5
11
NO
Giới hạn
  • $1 \le Q \le 10^5$
  • $|a|, |x| \le 10^6$, $|b| \le 10^{12}$
Draft saved