Cánh Đồng Chia Ô

Buổi 62 — Sqrt Decomposition & Mo
Points
15
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Một cánh đồng được chia thành N ô liên tiếp, ô thứ i có giá trị a_i. Có Q truy vấn, mỗi truy vấn cho hai số l, r, yêu cầu tính tổng các giá trị từ ô l đến ô r.

Hãy sử dụng phương pháp chia căn (sqrt decomposition) để trả lời các truy vấn.

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 chứa hai số nguyên l, r (1 ≤ l ≤ r ≤ N).

Dữ liệu ra

Với mỗi truy vấn, in ra tổng các giá trị từ ô l đến ô r trên một dòng.

Ví dụ
Input Output
5 3\n1 2 3 4 5\n1 3\n2 5\n1 5 6\n14\n15
Giới hạn
  • 1 ≤ N, Q ≤ 100000
  • 1 ≤ a_i ≤ 10^9
  • 1 ≤ l ≤ r ≤ N
Draft saved