Codeforces Round 921 (Div. 1) |
---|
Закончено |
На прямой линии расположены $$$n$$$ точек, пронумерованных от $$$1$$$ до $$$n$$$. Изначально существует $$$m$$$ гаваней, причем $$$i$$$-я гавань находится в точке $$$X_i$$$ и имеет значение $$$V_i$$$. Гарантируется, что в точках $$$1$$$ и $$$n$$$ существуют гавани. На каждой из $$$n$$$ точек находится ровно один корабль. Стоимость перемещения корабля с его текущего местоположения до следующей гавани равна произведению значения ближайшей гавани слева и расстояния до ближайшей гавани справа. В частности, если корабль уже находится в гавани, стоимость перемещения его до следующей гавани равна $$$0$$$.
Кроме того, имеется $$$q$$$ запросов, каждый из которых является одним из $$$2$$$ типов:
Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$q$$$ ($$$2 \le m \le n \le 3 \cdot 10^5$$$, $$$1 \le q \le 3 \cdot 10^5$$$) — количество точек, гаваней и запросов соответственно.
Вторая строка содержит $$$m$$$ различных целых чисел $$$X_1, X_2, \ldots, X_m(1 \le X_i \le n)$$$ — позиции $$$i$$$-й гавани.
Третья строка содержит $$$m$$$ целых чисел $$$V_1, V_2, \ldots, V_m(1 \le V_i \le 10^7)$$$ — значения $$$i$$$-й гавани.
Каждая из следующих $$$q$$$ строк содержит три целых числа. Первое целое число $$$t$$$ ($$$1\le t \le 2$$$) — тип запроса. Если $$$t=1$$$, то следующие два целых числа $$$x$$$ и $$$v$$$ ($$$2 \le x \le n - 1$$$, $$$1 \le v \le 10^7$$$) — запрос первого типа. Если $$$t=2$$$, то следующие два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$) — запрос второго типа.
Гарантируется, что есть хотя бы один запрос второго типа.
Для каждого запроса второго типа выведите одно целое число в новой строке — ответ на этот запрос.
8 3 41 3 83 24 102 2 51 5 152 5 52 7 8
171 0 15
Для первого запроса типа $$$2$$$, цена для кораблей на позициях $$$2$$$, $$$3$$$, $$$4$$$ и $$$5$$$ будет $$$3(3 \times 1)$$$, $$$0$$$, $$$96(24 \times 4)$$$ и $$$72(24 \times 3)$$$ соответственно.
Для второго запроса типа $$$2$$$, так как корабль в точке $$$5$$$ уже находится в гавани, ответ будет $$$0$$$.
Для третьего запроса типа $$$2$$$, цена для кораблей на позициях $$$7$$$ и $$$8$$$ будет $$$15(15 \times 1)$$$ и $$$0$$$ соответственно.
Название |
---|