Pháo Đài Bất Khả Xâm Phạm
Points
42
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề bài
Một pháo đài có N vị trí phòng thủ xếp thành hàng, vị trí thứ i có sức phòng thủ a_i. Có Q thao tác gồm hai loại:
- Loại 1:
1 l r v— tăng sức phòng thủ của tất cả vị trí từ l đến r thêm v. - Loại 2:
2 l r— hỏi tổng sức phòng thủ từ vị trí l đến r.
Sử dụng sqrt decomposition với lazy propagation cấp khối.
Dữ liệu vào
Dòng đầu chứa hai số nguyên N và Q (1 ≤ N, Q ≤ 100000). Dòng thứ hai chứa N số nguyên a_1, a_2, ..., a_N (0 ≤ a_i ≤ 10^9). Q dòng tiếp theo, mỗi dòng mô tả một thao tác.
Dữ liệu ra
Với mỗi truy vấn loại 2, in ra tổng sức phòng thủ trên một dòng.
Ví dụ
| Input | Output |
|---|---|
| 5 4\n1 2 3 4 5\n2 1 5\n1 2 4 10\n2 1 5\n2 2 4 | 15\n45\n39 |
Giới hạn
- 1 ≤ N, Q ≤ 100000
- 0 ≤ a_i ≤ 10^9
- Loại 1: 1 ≤ l ≤ r ≤ N, 1 ≤ v ≤ 10^9
- Loại 2: 1 ≤ l ≤ r ≤ N
Community Discussion