Массивын дэд хэсгийн нийлбэрийн хүсэлтүүд

2s

512MB

1475

0%

Range Queries

$n$ бүхэл тооноос бүрдсэн массив байна. Массивын зарим утгууд шинэчлэгдэх бөгөөд шинэчлэлт бүрийн дараа массивын дэд хэсгийн нийлбэрийн хамгийн их утгыг гаргана.

Эх сурвалж: cses.fi

Оролтын формат

Эхний мөрөнд $n$ ба $m$ бүхэл тоо байна: массивын хэмжээ ба шинэчлэлтүүдийн тоо. Массив $1,2,\ldots,n$ -ээр дугаарлагдана.

Хоёр дахь мөрөнд $n$ бүхэл тоо $x_1,x_2,\ldots,x_n$ байна: массивын анхны агуулга.

Дараа нь өөрчлөлтүүдийг тодорхойлсон $m$ мөр байна. Мөр бүрт $k$ ба $x$ хоёр бүхэл тоо байна: $k$ байрлалын утга $x$ болно.

Гаралтын формат

Шинэчлэлт бүрийн дараа дэд хэсгийн нийлбэрийн хамгийн их утгыг хэвлэ. Хоосон дэд хэсэг (нийлбэр $0$ -тэй) зөвшөөрөгддөг.

Хязгаарлалт

$1 \le n, m \le 2 \cdot 10^5$
$-10^9 \le x_i \le 10^9$
$1 \le k \le n$
$-10^9 \le x \le 10^9$

Жишээ

Оролт1

5 3
1 2 -3 5 -1
2 6
3 1
2 -2

Гаралт1

9
13
6

0.1 / 64 KiB

Редактор уншиж байна...