Segment Tree Lazy Cộng Đoạn
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho mảng gồm $N$ số nguyên $a_1, \dots, a_N$ và $Q$ truy vấn thuộc hai loại:
1 l r v: cộng thêm $v$ vào mọi phần tử từ chỉ số $l$ đến $r$.2 l r: tính tổng các phần tử từ chỉ số $l$ đến $r$.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N, Q$ ($1 \le N, Q \le 10^5$).
- Dòng thứ hai chứa $N$ số nguyên $a_1, \dots, a_N$ ($-10^6 \le a_i \le 10^6$).
- $Q$ dòng tiếp theo, mỗi dòng mô tả một truy vấn ($1 \le l \le r \le N$, $-10^6 \le v \le 10^6$).
Dữ liệu ra
- Với mỗi truy vấn loại 2, in ra tổng tìm được trên một dòng.
Ví dụ
| Input | Output |
|---|---|
| 4 3 1 2 3 4 1 1 4 10 2 1 4 2 2 2 |
50 12 |
Giới hạn
- $1 \le N, Q \le 10^5$, $-10^6 \le a_i, v \le 10^6$
Community Discussion