TLEoj Cup Final Day 1 - Truy vấn dãy tăng

Điểm: 2500 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: IAQ.inp

Output: IAQ.out

Tác giả:

Sunlight

Dạng bài

Bạn được cho một dãy $a$ có $n$ phần tử và bạn phải thực hiện hai loại truy vấn:

Loại 1: ! u v: Thay đổi giá trị của $a_u$ thành $v$ .
Loại 2: ? l r: Giả sử mỗi thao tác bạn có thể chọn một phần tử bất kỳ và tăng nó lên 1 đơn vị, tính số thao tác ít nhất để dãy con từ $l$ đến $r$ trở thành dãy không giảm (lưu ý: đây chỉ là thao tác tính toán thuần túy, không ảnh hưởng đến dãy $a$ ).

Bạn còn được cho một số $t$ , biểu thị độ phụ thuộc của các truy vấn loại 1. Nếu $t = 0$ thì các truy vấn loại 1 sẽ độc lập với nhau, hay nói cách khác, truy vấn loại 1 thứ $i - 1$ sẽ hết hiệu lực ngay trước khi thực hiện truy vấn loại 1 thứ $i$ . Nếu $t = 1$ , các truy vấn loại 1 sẽ cớ tác dụng vĩnh viễn.

Input, Output và Subtask

Input (IAQ.inp)

Dòng đầu tiên gồm ba số nguyên dương $n, t, q$ , miêu tả số phần tử của dãy $a$ , độ phụ thuộc giữa các truy vấn với nhau, và số lượng truy vấn. $(n, q \le 10^5)$
Dòng thứ hai gồm $n$ số nguyên mô tả dãy $a$ ban đầu $(a_i \le 10^9)$ .
$q$ dòng tiếp theo, mỗi dòng là một truy vấn có dạng như trên.

Output (IAQ.out)

Với mỗi truy ván loại 2, in ra kết quả cần tìm.

Subtask

$20\%$ số điểm có $n, q \le 2000$ .
$20\%$ số điểm khác không có truy vấn loại 1.
$20\%$ số điểm khác có $t = 0$ và $l = 1, r = n$ với mọi truy vấn loại 2.
$20\%$ số điểm khác có $t = 1$ và $l = 1, r = n$ với mọi truy vấn loại 2.
$20\%$ số điểm còn lại không có giới hạn gì thêm.

Sample 1

Input (IAQ.inp)

Output (IAQ.out)

3
1
2

Notes

Input (`IAQ.inp`)	Output (`IAQ.out`)	Note
`4 0 6`		$n = 4$ , $q = 6$ và các truy vấn là độc lập
`2 4 1 4`		$a = (2, 4, 1, 4)$
`! 2 4`		$a = (2, 4, 1, 4)$
`? 1 4`	`3`	Cần 3 thao tác để biến dãy $a$ thành $(2, 4, 4, 4)$
`! 3 3`		$a = (2, 4, 3, 4)$
`? 1 4`	`1`	Cần 1 thao tác để biến dãy $a$ thành $(2, 4, 4, 4)$
`! 2 1`		$a = (2, 1, 1, 4)$
`? 1 4`	`2`	Cần 2 thao tác để biến dãy $a$ thành $(2, 2, 2, 4)$

Sample 2

Input (IAQ.inp)

Output (IAQ.out)

2
1
2

Notes

Input (`IAQ.inp`)	Output (`IAQ.out`)	Note
`5 1 6`		$n = 5$ , $q = 6$ và các truy vấn phụ thuộc vào nhau
`2 10 4 2 5`		$a = (2, 10, 4, 2, 5)$
`? 3 5`	`2`	Cần 2 thao tác để biến dãy $(a_3, a_4, a_5)$ thành $(4, 4, 5)$
`! 3 3`		$a = (2, 10, 3, 2, 5)$
`? 3 5`	`1`	Cần 1 thao tác để biến dãy $(a_3, a_4, a_5)$ thành $(3, 3, 5)$
`! 2 4`		$a = (2, 4, 3, 2, 5)$
`! 4 6`		$a = (2, 4, 3, 6, 5)$
`? 1 5`	`2`	Cần 2 thao tác để biến dãy $a$ thành $(2, 4, 4, 6, 6)$

Bình luận đầu tiên

Bình luận

Không có bình luận nào.