Codeforces Round #804 (Div. 2)
4 өдрийн дараа |
C. Дзи Фибоначийн тоонуудад дуртай
хугацааны хязгаарлалт 4 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Математикийн үүднээс авч үзвэл Фибоначийн тоонуудын $F_{n}$ дараалал нь тодорхой давтамжтай холбоотой
$F_{1} = 1; F_{2} = 1; F_{n} = F_{n - 1} + F_{n - 2} (n > 2).$
Дзи Фибоначийн тоонуудад маш их дуртай. Өнөөдөр Дзи чамд $n$ бүхэл тоонуудаас бүрдсэн массив өгсөн: $a_{1}, a_{2}, ..., a_{n}$. Үүнээс гадна $m$ асуулгууд өгсөн ба асуулга бүр нь дараах хоёр төрлийн нэг байна:
- "$1 l r$" хэлбэрийн асуулга. Асуулгын хариу нь $l ≤ i ≤ r$ байх $F_{i - l + 1}$-н $a_{i}$ элемент бүрийг нэмэх хэрэгтэй.
- "$2 l r$" хэлбэрийн асуулга. Асуулгын хариу нь
модуль $1000000009 (10^{9} + 9)$ утга байх ёстой.
Бүх асуулгад хариулахад нь Дзид тусал.
Оролт
Эхний мөр нь $n$, $m$ ($1 ≤ n, m ≤ 300000$) хоёр бүхэл тоог агуулна. Хоёр дахь мөр нь анхны $a$ массив болох $n$ бүхэл $a_{1}, a_{2}, ..., a_{n} (1 ≤ a_{i} ≤ 10^{9})$ тоонуудыг агуулна.
Дараа нь $m$ мөрүүд байгаа. Нэг мөрөнд дээр өгөгдсөн хэлбэрийн нэг асуулга байна. Асуулга бүр нь $1 ≤ l ≤ r ≤ n$ тэнцэтгэл бишийг хангана.
Гаралт
Хоёр дахь хэлбэрийн асуулга бүрийн нийлбэрийн утгыг нэг мөрөнд хэвлэнэ.
Орчуулсан: Даариймаа
Жишээ тэстүүд
Оролт
4 4 1 2 3 4 1 1 4 2 1 4 1 2 4 2 1 3
Гаралт
17 12
Тэмдэглэл
Эхний асуулгын дараа, $a = [2, 3, 5, 7]$.
Хоёр дахь асуулга нь $sum = 2 + 3 + 5 + 7 = 17$.
Гуравдугаар асуулгын дараа, $a = [2, 4, 6, 9]$.
Дөрөвдүгээр асуулга, $sum = 2 + 4 + 6 = 12$.