Codeforces Round #FF (Div. 2)E (ライン セグメント ツリー セグメントの更新)_html/css_WEB-ITnose

C. DZY Loves Fibonacci Numbers

テストごとの制限時間

4 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

数学的表現この用語では、フィボナッチ数列 Fn は漸化式

F1?=?1; によって定義されます。 F2?=?1; Ｆｎ?＝?Ｆｎ?−?１?＋?Ｆｎ?−?２（ｎ?＞?２）。

DZY はフィボナッチ数式が大好きです。現在、DZY は、n 個の整数から構成される配列を提供します: a1、?a2、?...、?an。さらに、mQuery があり、各クエリには次の 2 つのタイプのいずれかがあります:

1. クエリの形式「1 l r」。クエリに応答して、各要素 ai に Fi?-?l?+?1 を追加する必要があります。ここで、l?≤?i?≤?r です。
2. クエリの形式は「2 l r」です。クエリへの応答として、モジュロ 1000000009 (109?+?9) の値を出力する必要があります。

DZY がすべてのクエリに応答できるようにします。

入力

入力の最初の行には、2 つの整数 n と 2 が含まれます。 m (1?≤?n,?m?≤?300000)。 2 行目には、n 個の整数、a1、?a2、?...、?an (1?≤?ai?≤?109)? が含まれています。初期配列 a.

その後、m 行が続きます。ステートメントで指定された形式で 1 ​​つのクエリを 1 行で記述します。各クエリについて、不等式 1?≤?l?≤?r?≤?n が成立することが保証されます。

出力

2 番目のタイプのクエリごとに、合計の値を 1 行に出力します。

サンプルテスト

入力

4 41 2 3 41 1 42 1 41 2 42 1 3

出力

1712

题意：サポート 2 操作、1 l ai加上第i-l+1项フィボナッチ数，l<=i<=r ，2 l r 求区间および

路思：フィボナッチ数列の性質に基づいて、ただ要知道前二项、那么可O（1）後面の任意のフィボナッチ数と任意の前部分を取得します项の和、ライン セグメントごとに、および各セグメントの前の 2 つのフィボナッチ数を使用できます。