DZY và dãy Fibonacci

Điểm: 8,00 (OI)

Giới hạn thời gian: 4.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++

Cho dãy Fibonacci được định nghĩa $F_{1} = 1$ , $F_{2} = 1$ , $F_{n} = F_{n - 1} + F_{n - 2}$ với mọi $n > 2$ .

Cho một mảng gồm $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ và $m$ truy vấn. Mỗi truy vấn thuộc một trong hai loại:

Cập nhật "1 l r": với mỗi $i$ thỏa $l \leq i \leq r$ , cộng thêm $F_{i - l + 1}$ vào $a_{i}$ .
Truy vấn "2 l r": in ra giá trị $(a_{l} + a_{l + 1} + \dots + a_{r}) mod (10^{9} + 9)$ .

Hãy xử lý tất cả các truy vấn theo thứ tự.

Dòng đầu tiên chứa hai số nguyên $n$ và $m$ .
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .
$m$ dòng tiếp theo, mỗi dòng mô tả một truy vấn theo định dạng nêu trên. Đảm bảo $1 \leq l \leq r \leq n$ .

Với mỗi truy vấn loại 2, in ra một dòng chứa giá trị tổng modulo $10^{9} + 9$ .

Input	Output	Giải thích
4 4 1 2 3 4 1 1 4 2 1 4 1 2 4 2 1 3	17 12	Sau truy vấn 1: mảng cộng thêm $F_{1}, F_{2}, F_{3}, F_{4} = 1, 1, 2, 3$ vào các vị trí 1..4, mảng thành $[2, 3, 5, 7]$ . Truy vấn 2 in tổng $2 + 3 + 5 + 7 = 17$ . Sau truy vấn 3: cộng $F_{1}, F_{2}, F_{3} = 1, 1, 2$ vào các vị trí 2..4, mảng thành $[2, 4, 6, 9]$ . Truy vấn 4 in tổng $2 + 4 + 6 = 12$ .
2 2 1 2 2 1 2 2 1 2	3 3	Không có cập nhật, mỗi truy vấn đều in tổng cả mảng $1 + 2 = 3$ .

Bình luận

Không có bình luận tại thời điểm này.