Sửa Chữa Nhà Máy

Điểm: 6,00 (OI)

Giới hạn thời gian: 4.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Một nhà máy sản xuất kim khâu hoạt động trong $n$ ngày. Bình thường nhà máy có thể sản xuất tối đa $a$ kim khâu mỗi ngày, nhưng do hỏng hóc nên hiện tại chỉ sản xuất được tối đa $b$ kim khâu mỗi ngày ( $b < a$ ). Chủ nhà máy muốn dành ra một khoảng $k$ ngày liên tiếp để sửa chữa: trong $k$ ngày đó nhà máy không sản xuất được gì, nhưng sau đó năng suất được khôi phục về $a$ kim khâu mỗi ngày.

Ban đầu chưa có đơn hàng nào. Nhà máy nhận được $q$ truy vấn, mỗi truy vấn thuộc một trong hai loại:

1 d a — có thêm $a$ đơn hàng đặt giao đúng vào ngày $d$ . Mỗi đơn hàng cần đúng một kim khâu được sản xuất trong ngày được đặt; nhà máy có thể chọn giao bao nhiêu đơn hàng tuỳ ý trong số đơn của ngày đó (không bắt buộc giao hết).
2 p — hỏi: nếu bây giờ nhà máy bắt đầu sửa chữa từ ngày $p$ (tức là không sản xuất trong các ngày $p, p + 1, \dots, p + k - 1$ ), thì tổng số đơn hàng nhiều nhất có thể được giao là bao nhiêu?

Cụ thể, với một ngày bất kỳ:

Nếu ngày đó nằm trước giai đoạn sửa chữa (ngày $< p$ ): tối đa $b$ đơn của ngày đó được giao.
Nếu ngày đó nằm trong giai đoạn sửa chữa ( $p \leq ngày \leq p + k - 1$ ): không giao được đơn nào.
Nếu ngày đó nằm sau giai đoạn sửa chữa (ngày $> p + k - 1$ ): tối đa $a$ đơn của ngày đó được giao.

Lưu ý các truy vấn loại 2 không thực sự xảy ra — chúng chỉ là câu hỏi giả định để chủ nhà máy cân nhắc thời điểm sửa chữa.

Dữ liệu vào

Dòng đầu chứa năm số nguyên $n$ , $k$ , $a$ , $b$ , $q$ .

$q$ dòng tiếp theo, mỗi dòng chứa một truy vấn dạng 1 d a_i hoặc 2 p như mô tả ở trên. Đảm bảo có ít nhất một truy vấn loại 2.

Dữ liệu ra

Với mỗi truy vấn loại 2, in ra trên một dòng số đơn hàng nhiều nhất có thể giao.

Ràng buộc

$1 \leq k \leq n \leq 2 \cdot 10^{5}$
$1 \leq b < a \leq 10^{4}$
$1 \leq q \leq 2 \cdot 10^{5}$
$1 \leq d \leq n$ , $1 \leq a_{i} \leq 10^{4}$
$1 \leq p \leq n - k + 1$

Ví dụ

Input	Output	Giải thích
5 2 2 1 8 1 1 2 1 5 3 1 2 1 2 2 1 4 2 1 3 2 2 1 2 3	3 6 4	Sau ba cập nhật đầu: đơn ngày 1=2, ngày 2=1, ngày 5=3. Truy vấn $p = 2$ (sửa ngày 2–3): ngày 1 giao $min (2, 1) = 1$ , ngày 4 giao 0, ngày 5 giao $min (3, 2) = 2$ → tổng 3. Sau hai cập nhật tiếp theo đơn ngày 3=2, ngày 4=2. Truy vấn $p = 1$ : chỉ tính ngày 3,4,5 với mức $a = 2$ , được $2 + 2 + 2 = 6$ . Truy vấn $p = 3$ : ngày 1,2 mức $b = 1$ được $1 + 1 = 2$ , ngày 5 mức $a = 2$ được 2, tổng 4.
5 4 10 1 6 1 1 5 1 5 5 1 3 2 1 5 2 2 1 2 2	7 1	$p = 1$ : chỉ tính ngày 5, $min (7, 10) = 7$ . $p = 2$ : chỉ tính ngày 1, $min (5, 1) = 1$ .

Bình luận

Không có bình luận tại thời điểm này.