Cuộc thi vẽ
Đề bài
Mô tả
Bạn đang tham gia một cuộc thi vẽ. Đề thi là vẽ một đường kẻ và điều khiển độ đậm (nét) của nó.
Đề thi được mô tả bằng một mảng gồm số nguyên, trong đó () là nét mong muốn tại vị trí thứ . Thí sinh vẽ từ trái sang phải theo các số này và điều khiển nét vẽ. Ví dụ, với (), đường kẻ mong muốn là cột thứ cao đúng ô.
Tuy nhiên, cây cọ rất khó điều khiển: một khi đã tăng nét, bạn không thể giảm nét xuống cho đến khi rửa cọ. Vì vậy, nét thực tế tại một vị trí bằng giá trị lớn nhất của các nét mong muốn từ lúc bắt đầu vẽ (hoặc từ lần rửa cọ gần nhất) đến vị trí đó. Mỗi ô vẽ thừa so với mong muốn là một ô sai (ô X). Với ví dụ trên, nét thực tế là , tức là số ô sai lần lượt ở các vị trí là .
Trong cuộc thi có một số thời điểm thí sinh phải rửa cọ, gọi là các điểm rửa cọ. Sau khi rửa cọ tại vị trí , nét vẽ được đặt lại ngay sau vị trí đó: từ vị trí , thí sinh bắt đầu vẽ lại với nét mong muốn. Ví dụ, nếu rửa cọ tại vị trí thứ và thứ , nét thực tế là .
Một bài con là đoạn liên tiếp của đề thi gốc (coi như đề thi chỉ gồm đoạn này cùng các điểm rửa cọ nằm trong nó tại thời điểm đó, các phần còn lại của đề gốc bị bỏ qua; nói riêng, việc vẽ bắt đầu tại vị trí ).
Điểm của bài con là số ô sai (số ô X) của bức vẽ.
Ví dụ, nếu không có điểm rửa cọ nào: . Nếu có hai điểm rửa cọ tại vị trí thứ và thứ : . Cũng với hai điểm rửa cọ này, (nét thực tế ) và .
Đề gốc quá dài và nhàm chán, nên ban tổ chức quyết định đưa ra lần lượt các yêu cầu sau (thay vì bắt hoàn thành cả đề gốc):
- Yêu cầu 1: thay đổi nét mong muốn tại một vị trí. Cho hai số và , gán . Thay đổi này được giữ lại.
- Yêu cầu 2: thêm một điểm rửa cọ mới tại vị trí . Đảm bảo vị trí chưa phải là điểm rửa cọ. Thay đổi này được giữ lại.
- Yêu cầu 3: yêu cầu thí sinh hoàn thành bài con .
Cho đề gốc và các yêu cầu, với mỗi yêu cầu loại 3 hãy in ra điểm của bài con đó.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và (): độ dài đề gốc và số yêu cầu.
- Dòng thứ hai chứa số nguyên (): đề gốc.
- dòng tiếp theo, mỗi dòng mô tả một yêu cầu theo một trong các dạng:
1 p x: gán nét mong muốn tại vị trí bằng (, ).2 p: thêm điểm rửa cọ tại vị trí (). Đảm bảo vị trí chưa phải là điểm rửa cọ, tức là không có hai yêu cầu loại 2 nào có cùng .3 l r: tính và in ra ().
Dữ liệu ra
Với mỗi yêu cầu loại 3, in ra đáp án trên một dòng.
Ràng buộc
- ,
- Không có hai yêu cầu loại 2 nào có cùng .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 10 11 1 3 2 1 4 2 3 1 2 3 3 1 10 2 8 2 3 3 1 10 3 6 9 3 8 10 1 8 5 1 6 4 1 7 1 3 6 9 3 8 10 |
12 7 2 0 3 0 |
Bốn đáp án đầu như trong đề bài. Sau ba yêu cầu loại 1, với điểm rửa cọ tại vị trí : nét thực tế , có ô sai. : nét đặt lại sau vị trí nên không có ô sai. |
| 8 6 1 2 4 1 6 2 4 3 3 2 4 2 6 3 1 8 1 4 3 1 5 1 3 3 5 |
3 8 4 |
: nét , có ô sai. với điểm rửa cọ tại : nét , có ô sai. Cuối cùng : có ô sai. |
Bình luận