Cây Li Chao Bền Vững

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

Bạn cần quản lý các phiên bản của một tập hợp đường thẳng. Ban đầu chỉ có phiên bản $0$ là tập rỗng. Có $Q$ truy vấn thuộc hai loại:

  • 1 v a b: Tạo một phiên bản mới (được đánh số tăng dần từ $1, 2, \dots$) bằng cách sao chép toàn bộ đường thẳng ở phiên bản $v$ và thêm đường thẳng $y = ax + b$.
  • 2 v x: Truy vấn giá trị nhỏ nhất của $ax + b$ tại hoành độ $x$ trong phiên bản $v$. Nếu phiên bản $v$ 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 loại 1 hoặc 2 ($v$ là chỉ số phiên bản hợp lệ đã tồn tại).
Dữ liệu ra
  • Với mỗi truy vấn loại 2, in ra kết quả hoặc NO trên một dòng.
Ví dụ
Input Output
7
1 0 2 1
1 1 -1 5
1 0 0 3
2 1 10
2 2 10
2 3 10
2 0 10
21
-5
3
NO
Giới hạn
  • $1 \le Q \le 10^5$
  • $|a|, |x| \le 10^6$, $|b| \le 10^{12}$
Draft saved