C. DZY Loves Fibonacci Numbers
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
in mathematical terms, the sequence fn of fibonacci numbers is defined by the recurrence relation
F1?=?1; F2?=?1; Fn?=?Fn?-?1?+?Fn?-?2 (n?>?2).
DZY loves Fibonacci numbers very much. Today DZY gives you an array consisting of n integers: a1,?a2,?…,?an. Moreover, there are mqueries, each query has one of the two types:
Format of the query “1 l r”. In reply to the query, you need to add Fi?-?l?+?1 to each element ai, where l?≤?i?≤?r. Format of the query “2 l r”. In reply to the query you should output the value of modulo 1000000009 (109?+?9).
Help DZY reply to all the queries.
Input
The first line of the input contains two integers n and m (1?≤?n,?m?≤?300000). The second line contains n integers a1,?a2,?…,?an (1?≤?ai?≤?109) ? initial array a.
Then, m lines follow. A single line describes a single query in the format given in the statement. It is guaranteed that for each query inequality 1?≤?l?≤?r?≤?n holds.
立即学习“前端免费学习笔记（深入）”；
Output
For each query of the second type, print the value of the sum on a single line.
Sample test(s)
input
4 41 2 3 41 1 42 1 41 2 42 1 3
登录后复制
output
1712
登录后复制
题意：支持两种操作，1 l r 将 ai 加上第i-l+1项Fibonacci数，l
思路：根据Fibonacci数列的性质，只要知道前两项，那么可以O（1）得到后面任意项的Fibonacci数以及任意前多少项的和，可以用线段树维护每个线段的和以及每段的前两
个Fibonacci数，延迟更新的是每个线段的前两个Fibonacci数（直接累加）
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/3092439.html
