33956번 - MMSQ

길이가 $N$인 정수 배열 $A$와 쿼리 $Q$개가 주어진다. 각 쿼리는 다음 두 종류 중 하나이다.

• 1 x v: $A_x$의 값을 $v$로 바꾼다.
• 2 l r: $max(i,j) =\max_{i\le k\le j}A_k$, $min(i,j) =\min_{i\le k\le j}A_k$, $sum(i,j) =\sum_{i\le k\le j}A_k$로 정의할 때, $\max_{l\le i\le j\le r}max(i,j) -min(i,j) +sum(i,j)$의 값을 출력한다.

모든 쿼리를 올바르게 처리하는 프로그램을 작성하여라.

첫 번째 줄에 배열의 길이 $N$과 쿼리의 개수 $Q$가 공백으로 구분되어 주어진다. $(1\le N,Q\le 100\, 000)$

두 번째 줄에 배열 $A$의 원소 $A_1,\cdots ,A_N$이 공백으로 구분되어 주어진다. $(-10^9\le A_i\le 10^9)$

세 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 아래와 같은 형식 중 하나로 주어진다.

• 1 x v $(1\le x\le N;-10^9\le v\le 10^9)$
• 2 l r $(1\le l\le r\le N)$

$2$번 쿼리가 하나 이상 주어진다.

각 $2$번 쿼리의 답을 한 줄에 하나씩 차례대로 출력한다.