Maison > interface Web > tutoriel HTML > Codeforces Round #FF (Div. 2)E(线段树成段更新)_html/css_WEB-ITnose

Codeforces Round #FF (Div. 2)E(线段树成段更新)_html/css_WEB-ITnose

WBOY
Libérer: 2016-06-24 11:58:38
original
923 Les gens l'ont consulté

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:

  1. 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.
  2. 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
Copier après la connexion

output

1712
Copier après la connexion

题意:支持两种操作,1 l r 将 ai 加上第i-l+1项Fibonacci数,l


思路:根据Fibonacci数列的性质,只要知道前两项,那么可以O(1)得到后面任意项的Fibonacci数以及任意前多少项的和,可以用线段树维护每个线段的和以及每段的前两


            个Fibonacci数,延迟更新的是每个线段的前两个Fibonacci数(直接累加)


Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal