statements segtree.pdf


Preview of PDF document statements-segtree.pdf

Page 1 2 3 4 5 6 7 8 9 10

Text preview


2012-2013 Òðåíèðîâêà ÑÏá Ó B Çàïðîñû íà îòðåçêå, äåðåâî îòðåçêîâ
ÂÊîíòàêòå, 2 îêòÿáðÿ 2012

Çàäà÷à A. Íàèâíûé RMQ
Èìÿ âõîäíîãî àéëà:
Èìÿ âûõîäíîãî àéëà:
Îãðàíè÷åíèå ïî âðåìåíè:
Îãðàíè÷åíèå ïî ïàìÿòè:

stupid_rmq.in
stupid_rmq.out
2 ñåêóíäû
256 ìåãàáàéò

Âàì äàí ìàññèâ a[℄ èç n ýëåìåíòîâ è m  êîëè÷åñòâî çàïðîñîâ, ñîñòîÿùèõ èç äâóõ ÷èñåë l è r ,
âûâåäèòå ìèíèìàëüíûé ýëåìåíò â ìàññèâå a[℄ ñ èíäåêñàìè îò l äî r .

Ôîðìàò âõîäíîãî àéëà

 ïåðâîé ñòðîêå âõîäíîãî àéëà ñîäåðæèòñÿ ÷èñëî n  äëèííà ìàññèâà a[℄ (1 6 n 6 1000). Âî
âòîðîé ñòðîêå ñîäåðæèòñÿ n ÷èñåë ai  ýëåìåíòû ìàññèâà (−109 6 ai 6 109 ).  ñëåäóþùåé ñòðîêå
ñîäåðæèòñÿ ÷èñëî m  êîëè÷åñòâî çàïðîñîâ (1 6 m 6 1000).  ïîñëåäíèõ m ñòðîêàõ ñîäåðæàòüñÿ
çàïðîñû l, r (1 6 l, r 6 n).

Ôîðìàò âûõîäíîãî àéëà

Äëÿ êàæäîãî çàïðîñà âûâåäèòå îòâåò â íîâîé ñòðîêå.

Ïðèìåðû

stupid_rmq.in

5
1 -2 3 4 1
3
1 3
3 4
1 5
2
-100000 -1111111
2
1 1
1 2

-2
3
-2

-100000
-1111111

Ñòðàíèöà 1 èç 6

stupid_rmq.out