Cập nhật đa thức bậc hai trên đoạn
Points
70
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Đề 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 rhoặc2 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$
Community Discussion