C. Дугуй $RMQ$

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

$a_0$, $a_1$, $...$, $a_{n-1}$ гэсэн дугуй дараалал өгөгдөв. Хоёр төрлийн үйлдэл хийж болно:

  • $inc(lf, rg, v)$ — энэ үйлдэл нь $[lf, rg]$ хэрчмийн бүх элементийг $v$ тоогоор өсгөнө;
  • $rmq(lf, rg)$ — энэ үйлдэл нь $[lf,rg]$ хэрчмийн элементүүдээс хамгийн багыг нь буцаана.

Дугуй хэрчим гэж, хэрвээ $n = 5$ ба $lf = 3$, $rg = 1$ бол энэ нь $3$, $4$, $0$, $1$ дугаартай дарааллыг ойлгоно.

Өгсөн үйлдлүүдийн дарааллын гүйцэтгэх програм бич.

Оролт

Эхний мөр $n$, ($1 ≤ n ≤ 200000$) бүхэл тоог агуулна. Дараагийн мөр анхны дараалал: $a_0$, $a_1$, $...$, $a_{n - 1}$ ($-10^6 ≤ a_i ≤ 10^6$) бүхэл тоонуудыг агуулна. Гуравдахь мөр үйлдлүүдийн тоо болох $m$ ($0 ≤ m ≤ 200000$) бүхэл тоог агуулна. Дараагийн $m$ мөр бүр нэг үйлдэл агуулна. Хэрвээ мөрөнд $lf$, $rg$ ($0 ≤ lf, rg ≤ n - 1$) хоёр бүхэл тоог агуулж байвал энэ нь $rmq$ үйлдэл, $lf$, $rg$, $v$ ($0 ≤ lf, rg ≤ n - 1$; $- 10^6 ≤ v ≤ 10^6$) гурван бүхэл тоог агуулж байвал энэ нь $inc$ үйлдэл гэж ойлгоно.

Гаралт

$rmq$ үйлдэл бүрт түүний үр дүнг бич.

Орчуулсан: Sugardorj

Жишээ тэстүүд

Оролт
4
1 2 3 4
4
3 0
3 0 -1
0 1
2 1
Гаралт
1
0
0
Сэтгэгдлүүдийг ачааллаж байна...