헬

면접 대비

시간 제한4초메모리 제한1024 MB

요약

점 갱신이 있는 배열에서 구간마다 원소 하나에 k를 곱했을 때 얻을 수 있는 최대 통증 값을 구합니다.

난이도: 보통10점 중 5점
유형: 세그먼트 트리, 배열, 그리디
정답자: 아직 제출이 없습니다

문제

헬은 죽은 자들의 여왕이다. 얼굴의 한쪽 절반은 피처럼 붉고, 다른 쪽 절반은 짙은 남청색에 가깝게 검다. 이런 외모에서 생긴 열등감 때문에 그녀는 포로를 조롱하는 것을 매우 즐긴다.

포로들은 한 줄로 서 있고 1부터 $n$ 까지 번호가 붙어 있다. 각 포로에게는 지금 고통받고 있는 온도가 있다. 헬은 언제든지 어떤 포로의 온도든 다른 값으로 바꿀 수 있다.

가끔 헬은 특정 구간을 잠깐 고문하기로 한다. 이때 구간 안 포로 한 명의 온도를 $k$ 배 한다. 고문이 끝나면 그 포로의 온도는 원래대로 돌아온다. 구간의 고통은 구간 안 모든 포로 온도 절댓값의 합이다. 헬은 고문하기로 한 구간마다 그 고통을 최대한 키우고 싶어 한다.

입력

첫 줄에 포로의 수 $n$ ( $1 \le n \le 300000$ )이 주어진다. 둘째 줄에는 $i$ 번째 포로의 온도 $a_i$ ( $-10^8 \le a_i \le 10^8$ )가 $n$ 개 주어진다. 셋째 줄에는 질의의 수 $m$ ( $1 \le n \le 300000$ )이 주어진다. 이어지는 $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배 하는 것이 유리하다.

예제2

예제 1
입력
```
3
1 2 3
2
assign 2 4
torture 2 3 3
```
예상 출력
```
15
```

예제 2

입력

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

예상 출력