Lệnh Từ Tướng Quân
Points
22
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề bài
Tướng quân có N binh sĩ đứng thành hàng, binh sĩ thứ i có sức mạnh a_i. Tướng quân phát Q lệnh, mỗi lệnh có dạng:
- Loại 1:
1 l r v— tăng sức mạnh của tất cả binh sĩ từ vị trí l đến r thêm v. - Loại 2:
2 i— hỏi sức mạnh hiện tại của binh sĩ thứ i.
Sử dụng sqrt decomposition để xử lý hiệu quả.
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 (1 ≤ a_i ≤ 10^9). Q dòng tiếp theo, mỗi dòng mô tả một lệnh theo định dạng trên.
Dữ liệu ra
Với mỗi truy vấn loại 2, in ra sức mạnh hiện tại của binh sĩ thứ i trên một dòng.
Ví dụ
| Input | Output |
|---|---|
| 5 5\n1 2 3 4 5\n2 3\n1 2 4 10\n2 3\n1 1 5 5\n2 5 | 3\n13\n10 |
Giới hạn
- 1 ≤ N, Q ≤ 100000
- 1 ≤ a_i ≤ 10^9
- Loại 1: 1 ≤ l ≤ r ≤ N, 1 ≤ v ≤ 10^9
- Loại 2: 1 ≤ i ≤ N
Community Discussion