Cập nhật đa thức bậc hai trên đoạn

Mathematics
Points
70
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Cho mảng $A$ gồm $N$ phần tử ban đầu đều bằng $0$, đánh số từ $1$ đến $N$. Thực hiện $Q$ truy vấn thuộc hai loại:

  • 1 l r: Với mọi $i \in [l, r]$, cộng thêm $(i - l + 1)^2$ vào $A[i]$.
  • 2 l r: Tính tổng $\sum_{i=l}^{r} A[i] \pmod{10^9 + 7}$.
Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $N$ và $Q$.
  • $Q$ dòng tiếp theo, mỗi dòng chứa một truy vấn dạng 1 l r hoặc 2 l r.
Dữ liệu ra

Với mỗi truy vấn loại 2, in ra kết quả theo modulo $10^9 + 7$ trên một dòng.

Ví dụ
Input Output
5 4
1 2 4
2 1 5
1 3 5
2 2 4
14
19
Giới hạn
  • $1 \le N, Q \le 10^5$
  • $1 \le l \le r \le N$
Draft saved