Das Suchen eines Arrays nach Ganzzahlen in einem bestimmten Bereich

Question

Kann jemand Ideen für das folgende Problem geben?

Gegeben sei ein Array ar[] der Länge n und einige Abfragen. Jede Abfrage hat die Form a, b, c, finde die Zahl mit dem kleinsten Index i, so dass der Index im Bereich [c, n] liegt und so dass a < ar[i] < b. Insgesamt gibt es (n - 1), c geht von 1 bis n - 1. Die erwartete Komplexität für jede Abfrage sollte ungefähr O(log n) betragen, und eine Vorverarbeitung mit einer maximalen Komplexität von höchstens O(n log n) ist angemessen. Intuitiv kam mir ein Segmentbaum in den Sinn, aber ich konnte mir keine Möglichkeit vorstellen, ihn zu erstellen, noch was in jedem Knoten gespeichert werden sollte.

Answer 1

Wenn ich das richtig lese, gibt es n-1 Abfragen, bei denen sich nur c ändert, In diesem Fall warum lösen Sie die Abfragen nicht rückwärts? Nimm zuerst die letzte Abfrage, da sie das letzte Element des Arrays betrifft. Überprüfe, ob das Element zwischen a und b liegt. Wenn ja, speichere das Ergebnis in einem Array ans[n-1]=n-1, ansonsten setzen wir ans[n-1]=-1, für jede nächste Abfrage j von n-2 bis 0

Wenn a[j] nicht zwischen a und b liegt 
     ans[j] = ans[j+1] 
sonst 
     ans[j] = j

All dies kann in O(n) erledigt werden.