Segment Tree Lazy Cộng Đoạn

Buổi 75-76 — Stress Test
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$
Draft saved