시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 239 57 44 23.404%

문제

길이 N의 정수 수열 K1, K2, ..., KN과 상수 UV가 주어진다.

Q개의 쿼리가 주어지며, 그 종류는 두 가지가 있다.

  1. AB가 주어지면, max(U × (Ki + Ki + 1 + ... + Kj) + V × (j - i)) (A ≤ i ≤ j ≤ B) 의 값을 구한다.
  2. AB가 주어지면, KA의 값을 B으로 바꾼다.

입력

첫 번째 줄에 정수 N과 QUV가 입력된다. (1 ≤ N, Q ≤ 105,  - 5 ≤ U, V ≤ 5)

두 번째 줄에 정수 A1, A2, ..., AN이 주어진다. (-102 ≤ Ai ≤ 102)

세 번째 줄부터 쿼리가 주어진다. 세 정수 CAB가 주어진다. (0 ≤ C ≤ 1, A, B, C는 정수)

C가 0이면 첫 번째 쿼리를, 아니면 두 번째 쿼리를 수행한다. 첫 번째 쿼리일 경우 1 ≤ A ≤ B ≤ N 이다. 두 번째 쿼리일 경우 1 ≤ A ≤ N, -102 ≤ B ≤ 102이다.

출력

한 줄마다 첫 번째 쿼리의 결과값을 출력한다.

예제 입력 1

5 3 2 4
1 1 1 1 1
0 1 5
1 3 -2
0 1 5

예제 출력 1

26
20

출처

Contest > 웰노운컵 > 제 1회 웰노운컵 A2번