Cây Phân Đoạn Li Chao

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

Cho $N$ vị trí đánh số từ $1$ đến $N$, ban đầu mỗi vị trí không chứa đường thẳng nào. Bạn cần xử lý $Q$ truy vấn thuộc hai loại:

  • 1 p a b: Thêm đường thẳng $y = ax + b$ vào vị trí $p$ ($1 \le p \le N$).
  • 2 L R x: Tìm giá trị nhỏ nhất của $ax + b$ tại hoành độ $x$ xét trên tất cả các đường thẳng nằm ở các vị trí thuộc đoạn $[L, R]$. Nếu không có đường thẳng nào trong đoạn $[L, R]$, in ra NO.
Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $N, Q$ ($1 \le N, 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.
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
4 6
1 1 2 5
1 3 -1 10
2 1 2 4
2 2 4 4
2 4 4 0
2 1 4 10
13
6
NO
0
Giới hạn
  • $1 \le N, Q \le 10^5$
  • $|a|, |x| \le 10^6$, $|b| \le 10^{12}$
Draft saved