D. k-хамгийн их дэд дарааллын нийлбэр

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

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

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

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

$a_{1}, a_{2}, ..., a_{n}$ бүхэл тоон дарааллыг авч үзье. Та хоёр төрлийн хүсэлтүүд дээр ажиллах ёстой:

  • "0 $i$ $val$" хэлбэрийн хүсэлт. Энэ хүсэлтийн хариунд та $a_{i} = val$ үйлдлийг хийх хэрэгтэй.
  • "1 $l$ $r$ $k$" хэлбэрийн хүсэлт. Энэ хүсэлтийн хариуд та $a_{l}, a_{l + 1}, ..., a_{r}$ дарааллаас хамгийн ихдээ $k$ ширхэг үл огтлолцох дэд хэсгийн хамгийн их нийлбэрийг хэвлэх ёстой. Томъёолбол та $(a_{x_1} + a_{x_1 + 1} + ... + a_{y_1}) + (a_{x_{2}} + a_{x_{2} + 1} + ... + a_{y_2}) + ... + (a_{x_t} + a_{x_{t} + 1} + ... + a_{y_t})$ нийлбэр хамгийн их байхаар, хамгийн ихдээ $k$ ширхэг $(x_{1}, y_{1}), (x_{2}, y_{2}), ..., (x_{t}, y_{t})$ $(l ≤ x_{1} ≤ y_{1} < x_{2} ≤ y_{2} < ... < x_{t} ≤ y_{t} ≤ r; t ≤ k)$ бүхэл тоон хосуудыг сонгох ёстой. Хамгийн ихдээ $k$ дэд хэсэг сонгох ёстойг анхаарна уу. Тухайлбал та $0$ дэд хэсэг сонгож болно. Энэ тохиолдолд тодорхойлсон нийлбэрийг тэгтэй тэнцүү гэж үзнэ.

Оролт

Эхний мөр нь $n$ $(1 ≤ n ≤ 10^{5})$ бүхэл тоог агуулах ба дараалалд хэдэн тоо байхыг харуулна. Дараагийн мөрөнд $n$ ширхэг $a_{1}, a_{2}, ..., a_{n}$ $(|a_{i}| ≤ 500)$ бүхэл тоонууд байна.

Гурав дахь мөр нь хүсэлтүүдийн тоо болох $m$ $(1 ≤ m ≤ 10^{5})$ бүхэл тоог агуулна. Дараагийн $m$ мөрүүд нь доор өгөгдсөн хэлбэрээр хүсэлтүүд агуулна.

Хүсэлтүүдийн бүх өөрчлөлт нь $1 ≤ i ≤ n$; $|val| ≤ 500$ хязгаарлалтанд багтана.

Хамгийн ихдээ $k$ ширхэг үл огтлолцох дэд хэсгийн хамгийн их нийлбэрийг тооцохдоо $1 ≤ l ≤ r ≤ n$; $1 ≤ k ≤ 20$ хязгаарлалтанд багтаана. $k$ ширхэг үл огтлолцох дэд хэсгийн хамгийн их нийлбэрийг тооцдог хүсэлтүүдийн тоо $10000$-аас хэтрэхгүй байна.

Гаралт

"$1$ $l$ $r$ $k$" хэлбэрийн хүсэлт бүрийн нийлбэрийг хэвлэнэ. Хүсэлтүүдийг оруулсан дарааллаар хариуг хэвлэнэ.

Орчуулсан: Даариймаа

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

Оролт
9
9 -8 9 -1 -1 -1 9 -8 9
3
1 1 9 1
1 1 9 2
1 4 6 3
Гаралт
17
25
0
Оролт
15
-4 8 -3 -10 10 4 -7 -7 0 -6 3 8 -10 7 2
15
1 3 9 2
1 6 12 1
0 6 5
0 10 -7
1 4 9 1
1 7 9 1
0 10 -3
1 4 10 2
1 3 13 2
1 4 11 2
0 15 -9
0 13 -9
0 11 -10
1 5 14 2
1 6 12 1
Гаралт
14
11
15
0
15
26
18
23
8

Тэмдэглэл

Эхний жишээний эхний хүсэлтэд та нэг ширхэг хос $(1, 9)$-г сонгож чадна. Тиймээс тодорхойлсон нийлбэр $17$ байна.

Эхний жишээний хоёр дахь хүсэлтийг харцгаая. Хэрхэн хоёр дэд хэсгийг сонгох вэ? $(1, 3)$ ба $(7, 9)$? Мэдээж үгүй, Бид $(1, 3)$ ба $(7, 9)$-ээс $20$ гэсэн нийлбэр гаргаж авна, үүний оронд илүү оновтой нийлбэр нь $25$ байх $(1, 7)$ ба $(9, 9) дэд хэсгийг сонгон авч болно$.

Гурав дахь хүсэлтийн хариу $0$, өгөгдсөн интервал дахь бүх тоо сөрөг бол бид сонгохгүй байхыг илүүд үзнэ.

Сэтгэгдлүүдийг ачааллаж байна...