Giải Đấu Động Học

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

Cho $N$ hàm bậc nhất $y_i(t) = a_i t + b_i$ ($1 \le i \le N$). Bạn cần xử lý $Q$ truy vấn thuộc hai loại:

  • 1 i a b: Cập nhật hàm thứ $i$ thành $y_i(t) = a t + b$.
  • 2 t: Tìm giá trị nhỏ nhất $\min_{1 \le i \le N} y_i(t)$ tại thời điểm $t$.

Biết rằng các giá trị $t$ trong truy vấn loại 2 xuất hiện theo thứ tự không giảm.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $N, Q$ ($1 \le N, Q \le 10^5$).
  • $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_i, b_i$ ban đầu.
  • $Q$ dòng cuối, 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ả trên một dòng.
Ví dụ
Input Output
3 5
5 0
2 10
-1 30
2 0
2 5
1 1 -3 20
2 5
2 10
0
20
5
-10
Giới hạn
  • $1 \le N, Q \le 10^5$
  • $|a_i|, |t| \le 10^6$, $|b_i| \le 10^{12}$
Draft saved