Bao Lồi Tuyến Tính Trực Tuyến

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

Xử lý trực tuyến $Q$ truy vấn trên một tập đường thẳng ban đầu rỗng:

  • 1 a b: Thêm đường thẳng $y = ax + b$ với hệ số góc $a$ bất kỳ.
  • 2 x': Giải mã hoành độ thực $x = x' \oplus (|\text{last}| \bmod 2^{20})$, trong đó $\text{last}$ là kết quả của truy vấn loại 2 gần nhất (ban đầu $\text{last} = 0$, $\oplus$ là phép XOR bit). Sau đó tìm giá trị lớn nhất của $ax + b$ tại $x$ trong tập đường thẳng hiện có.
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.
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
4
1 2 3
1 -1 10
2 5
2 4
13
21
Giới hạn
  • $1 \le Q \le 10^5$
  • $|a|, |x'| \le 10^6$, $|b| \le 10^{12}$
Draft saved