Pháo Đài Bất Khả Xâm Phạm

Buổi 62 — Sqrt Decomposition & Mo
Points
42
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề 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
Draft saved