| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 1024 MB | 17 | 14 | 10 | 76.923% |
Хель --- владычица мертвых, одна половина ее лица кроваво-красная, другая же иссиня-черная. В связи с комплексом неполноценности, развившемся из-за такой внешности, она очень любит издеваться над своими узниками.
Все ее узники стоят в ряд и занумерованы от 1 до $n$. Каждый узник имеет свою температуру, при которой он в данный момент мучается. Хель может в любой момент поменять температуру любого узника на некоторую другую.
Иногда Хель решает кратковременно помучить конкретный отрезок. При этом она умножает на $k$ температуру одного из узников на отрезке. После этого мучения температура этого узника снова придет к первоначальной. При этом боль отрезка вычисляется как сумма модулей температур каждого узника на этом отрезке. Теперь Хель хочется максимально увеличить боль каждого отрезка, который она захотела помучить.
В первой строке дано число $n$ (1ドル \le n \le 300,000円$) --- количество узников. Во второй строке находятся $n$ чисел $a_i$ ($-10^8 \le a_i \le 10^8$) --- температура i-го узника. В третьей строке находится число $m$ (1ドル \le n \le 300,000円$) --- количество запросов. Далее в $m$ строках следуют запросы вида
assign>> $x$ $t$ (1ドル \le x \le n,ドル $-10^8 \le t \le 10^8$) --- заменить температуру узника с номером $x$ на $t$torture>> $l$ $r$ $k$ (1ドル \le l \le r \le n,ドル $-10^8 \le k \le 10^8$) --- начать мучить отрезок, начиная с узника с номером $l$ и заканчивая узником с номером $r,ドル умножив температуру одного из узников этого отрезка на $k$Для каждого запроса <<torture>> выведите максимальную боль отрезка, которую можно получить.
3 1 2 3 2 assign 2 4 torture 2 3 3
15
6 -1 -6 0 5 3 -3 9 assign 1 -9 torture 1 1 7 assign 2 9 torture 1 2 -9 torture 3 5 -6 torture 3 6 0 assign 3 -1 torture 5 6 9 torture 6 6 0
-63 90 8 8 24 0
В первом примере Хель выгодно умножить на три температуру второго узника.