Cập nhật bậc thang trên đoạn

Arrays Buổi 15 — Prefix Sum & Difference Array prefix-sum
Points
33
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Submissions
Đề bài

Cho mảng $A$ gồm $N$ phần tử ban đầu đều bằng $0$. Thực hiện $Q$ thao tác, mỗi thao tác cho hai số nguyên $L, R$ ($1 \le L \le R \le N$), yêu cầu cộng $1$ vào $A_L$, cộng $2$ vào $A_{L+1}$, ..., cộng $(R - L + 1)$ vào $A_R$. Hãy in ra các phần tử của mảng $A$ sau $Q$ thao tác, lấy phần dư khi chia cho $10^9 + 7$.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N, Q$. $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $L, R$.

Dữ liệu ra

In ra $N$ số nguyên là mảng $A$ sau các thao tác (theo modulo $10^9 + 7$), cách nhau bởi dấu cách.

Ví dụ
Input Output
5 2
1 4
3 5
1 2 4 6 3
4 1
2 4
0 1 2 3
Giới hạn

$1 \le N \le 10^5$, $0 \le Q \le 10^5$.

Draft saved