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

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

Jun 24, 2016 am 11:58 AM
round 更新

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
Nach dem Login kopieren

output

1712
Nach dem Login kopieren

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


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


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


Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Heiße KI -Werkzeuge

Undresser.AI Undress

Undresser.AI Undress

KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover

AI Clothes Remover

Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool

Undress AI Tool

Ausziehbilder kostenlos

Clothoff.io

Clothoff.io

KI-Kleiderentferner

AI Hentai Generator

AI Hentai Generator

Erstellen Sie kostenlos Ai Hentai.

Heißer Artikel

R.E.P.O. Energiekristalle erklärten und was sie tun (gelber Kristall)
2 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
Repo: Wie man Teamkollegen wiederbelebt
4 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Abenteuer: Wie man riesige Samen bekommt
4 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌

Heiße Werkzeuge

Notepad++7.3.1

Notepad++7.3.1

Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version

SublimeText3 chinesische Version

Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1

Senden Sie Studio 13.0.1

Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6

Dreamweaver CS6

Visuelle Webentwicklungstools

SublimeText3 Mac-Version

SublimeText3 Mac-Version

Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Wie kann man das Problem beheben, dass das Blizzard Battle.net-Update bei 45 % hängen bleibt? Wie kann man das Problem beheben, dass das Blizzard Battle.net-Update bei 45 % hängen bleibt? Mar 16, 2024 pm 06:52 PM

Blizzard Battle.net-Update bleibt bei 45 % hängen, wie kann man das Problem lösen? In letzter Zeit stecken viele Leute beim Aktualisieren der Software fest. Sie bleiben auch nach mehrmaligem Neustart stecken. Wie können wir diese Situation lösen? In diesem Software-Tutorial werden die Bedienungsschritte erläutert, in der Hoffnung, mehr Menschen zu helfen. Das Blizzard Battle.net-Update bleibt bei 45 % hängen. Wie lässt sich das Problem lösen? 1. Client 1. Zuerst müssen Sie bestätigen, dass es sich bei Ihrem Client um die offizielle Version handelt, die von der offiziellen Website heruntergeladen wurde. 2. Wenn nicht, können Benutzer zum Herunterladen die asiatische Server-Website aufrufen. 3. Klicken Sie nach der Eingabe oben rechts auf „Herunterladen“. Hinweis: Achten Sie darauf, bei der Installation nicht Vereinfachtes Chinesisch auszuwählen.

Update von Epic Seven vom 22. Februar: Die zweite Woche von Miracle Maid Kingdom beginnt Update von Epic Seven vom 22. Februar: Die zweite Woche von Miracle Maid Kingdom beginnt Feb 21, 2024 pm 05:52 PM

Es wurde bestätigt, dass Epic Seven am 22. Februar um 11 Uhr mittags kontinuierlich aktualisiert wird. Dieses Update wird uns viele neue Aktivitäten und Inhalte bringen, darunter eine Erhöhung der begrenzten Beschwörungsrate von Leia und Sweet Miracle sowie ein Update des mysteriösen Kartenpools , Die zweite Woche der besonderen Nebengeschichte Miracle Maid Kingdom hat begonnen. Update-Zeitplan für Mobilspiele: The Seventh Epic wird am 22. Februar aktualisiert: Das Miracle Maid Kingdom wird für die zweite Woche geöffnet ※Die Chance auf eine begrenzte Beschwörung von „Leia“ und „Sweet Miracle“ ist hoch! ■Begrenzte Beschwörungschance. Startzeit: -22.02.2024 (Donnerstag) 11:00 ~ 07.03.2024 (Donnerstag) 10:59 ■Charakterattribute und -berufe: Natürliche Attribute, Krieger ■Charaktereinführung: Vier-Personen-Band The Subsänger von „Miracle Maid Kingdom“ und Bei

Einfache Schritte zum Aktualisieren der Pip-Version: in 1 Minute erledigt Einfache Schritte zum Aktualisieren der Pip-Version: in 1 Minute erledigt Jan 27, 2024 am 09:45 AM

In einer Minute erledigt: So aktualisieren Sie die Pip-Version. Mit der rasanten Entwicklung von Python ist Pip zu einem Standardtool für die Python-Paketverwaltung geworden. Mit der Zeit werden die Pip-Versionen jedoch ständig aktualisiert. Um die neuesten Funktionen nutzen und mögliche Sicherheitslücken schließen zu können, ist es sehr wichtig, die Pip-Version zu aktualisieren. In diesem Artikel wird erläutert, wie Sie Pip in einer Minute schnell aktualisieren können, und es werden spezifische Codebeispiele bereitgestellt. Zuerst müssen wir ein Befehlszeilenfenster öffnen. In Windows-Systemen können Sie verwenden

So installieren Sie Angular unter Ubuntu 24.04 So installieren Sie Angular unter Ubuntu 24.04 Mar 23, 2024 pm 12:20 PM

Angular.js ist eine frei zugängliche JavaScript-Plattform zum Erstellen dynamischer Anwendungen. Es ermöglicht Ihnen, verschiedene Aspekte Ihrer Anwendung schnell und klar auszudrücken, indem Sie die Syntax von HTML als Vorlagensprache erweitern. Angular.js bietet eine Reihe von Tools, die Sie beim Schreiben, Aktualisieren und Testen Ihres Codes unterstützen. Darüber hinaus bietet es viele Funktionen wie Routing und Formularverwaltung. In dieser Anleitung wird erläutert, wie Angular auf Ubuntu24 installiert wird. Zuerst müssen Sie Node.js installieren. Node.js ist eine JavaScript-Ausführungsumgebung, die auf der ChromeV8-Engine basiert und es Ihnen ermöglicht, JavaScript-Code auf der Serverseite auszuführen. In Ub sein

So beheben Sie den Aktualisierungsfehler 0x80004002 für Win10 Version 2004 So beheben Sie den Aktualisierungsfehler 0x80004002 für Win10 Version 2004 Jan 10, 2024 am 09:25 AM

Wenn unser Computer mit einem Win10-System installiert ist und für die Aktualisierung auf Win102004 bereit ist, schlägt das während des Updates angezeigte Update auf Win10 Version 2004 fehl und gibt den Fehlercode 0x80004002 aus. Der Herausgeber geht davon aus, dass es an einigen Ungenauigkeiten in unserem System liegt Das durch die Fehlerbehebung verursachte Problem kann in der Eingabeaufforderung behoben werden. Für detaillierte Lösungsschritte schauen wir uns an, was der Editor getan hat ~ So lösen Sie das Problem des Aktualisierungsfehlers 0x80004002 für Win10 Version 2004 Lösung 1: „Sauberer Neustart“, um den Einfluss von Software von Drittanbietern zu beseitigen: 1. Stoppen Sie nicht zum Kern gehörende Software Programmvorgänge (einschließlich der ersten Antiviren- und Optimierungssoftware von Drittanbietern) 2. Wenn die Umstände es zulassen, deinstallieren Sie Antivirenprogramme von Drittanbietern vom Gerät

Wie aktualisiere ich den MSI-Grafikkartentreiber? Schritte zum Herunterladen und Installieren des MSI-Grafikkartentreibers Wie aktualisiere ich den MSI-Grafikkartentreiber? Schritte zum Herunterladen und Installieren des MSI-Grafikkartentreibers Mar 13, 2024 pm 08:49 PM

MSI-Grafikkarten sind die Mainstream-Grafikkartenmarke auf dem Markt. Wir wissen, dass Grafikkarten Treiber installieren müssen, um Leistung zu erzielen und Kompatibilität sicherzustellen. Wie aktualisiere ich den MSI-Grafikkartentreiber auf die neueste Version? Im Allgemeinen können MSI-Grafikkartentreiber von der offiziellen Website heruntergeladen und installiert werden. Methode zur Aktualisierung des Grafikkartentreibers: 1. Zuerst rufen wir die „offizielle MSI-Website“ auf. 2. Klicken Sie nach der Eingabe auf die Schaltfläche „Suchen“ in der oberen rechten Ecke und geben Sie Ihr Grafikkartenmodell ein. 3. Suchen Sie dann die entsprechende Grafikkarte und klicken Sie auf die Detailseite. 4. Geben Sie dann oben die Option „Technischer Support“ ein. 5. Gehen Sie abschließend zu „Treiber & Download“

Lantern und Dungeon am 29. Februar aktualisiert: Remastered-Version ╳ „Legend of Nezha'-Verknüpfung Lantern und Dungeon am 29. Februar aktualisiert: Remastered-Version ╳ „Legend of Nezha'-Verknüpfung Feb 28, 2024 am 08:13 AM

Es wurde bestätigt, dass Lantern and Dungeons am 29. Februar aktualisiert wird. Nach dem Update wird die remasterte Version auch mit Legend of Nezha verknüpft sein Beruf, und Spieler können direkt Jobwechsel durchführen, Dungeon-Inhalte werden ebenfalls erweitert, neue Dungeon-Bereiche werden eröffnet usw. Aktualisierungsplan für Mobilspiele Lantern und Dungeon am 29. Februar aktualisiert: Remastered-Version ╳ Schlüsselinhalt der Verknüpfungsversion „Legend of Nezha“ Neuer Beruf, warum werden Sie eingeladen, den Job zu wechseln? Solch coole Ausrüstung macht die Leute wirklich gierig Ich habe gehört, dass der Laternenhalter nach einem Jobwechsel auch viele coole Fähigkeiten erlernen kann: Thaihosen sind heiß! Die Legende von Nezha kommt zusammen! Auf das heiße Rad steigen und den Kreis aus Himmel und Erde in der Hand halten ♫ ~ Die kleinen Helden mit Weisheit und Mut: Nezha und Little Dragon Girl stehen vor der Tür

Windows kann nicht auf das angegebene Gerät, den angegebenen Pfad oder die angegebene Datei zugreifen Windows kann nicht auf das angegebene Gerät, den angegebenen Pfad oder die angegebene Datei zugreifen Jun 18, 2024 pm 04:49 PM

Der Computer eines Freundes weist einen solchen Fehler auf. Beim Öffnen von „Dieser PC“ und der Datei auf Laufwerk C wird die Meldung „Explorer.EXE“ angezeigt. Windows kann nicht auf das angegebene Gerät, den angegebenen Pfad oder die angegebene Datei zugreifen. Möglicherweise verfügen Sie nicht über die entsprechenden Berechtigungen, um auf das Projekt zuzugreifen. " Einschließlich Ordner, Dateien, Dieser Computer, Papierkorb usw. wird durch Doppelklicken ein solches Fenster geöffnet, es ist jedoch normal, es durch Klicken mit der rechten Maustaste zu öffnen. Dies wird durch ein Systemupdate verursacht. Wenn Sie ebenfalls auf diese Situation stoßen, erfahren Sie im folgenden Editor, wie Sie das Problem lösen können. 1. Öffnen Sie den Registrierungseditor Win+R und geben Sie regedit ein, oder klicken Sie zum Ausführen mit der rechten Maustaste auf das Startmenü und geben Sie regedit ein. 2. Suchen Sie die Registrierung „Computer\HKEY_CLASSES_ROOT\PackagedCom\ClassInd“;

See all articles