ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#6122

센터가 돋보여야 해 3s 512MB

問題

나코더 39기 부원인 정후는 2022년 솔대제에 나코더의 무대를 선보이려고 한다. 무대의 이름은 '수열과 쿼리 333'으로, 1번부터 N번까지 일렬로 서 있는 학생들이 정후가 만든 Q가지 동작을 보여 줄 것이다. 각 동작은 두 종류 중 하나이고, 각 학생은 하나의 정수로 나타내어지는 매력을 가지고 있다.

  • 첫 번째 종류의 동작은 x_i번 학생의 매력을 y_i로 바꾼다.

  • 두 번째 종류의 동작은 l_i번 학생과 r_i번 학생 사이에서 서로 다른 학생 세 명이 나와 무대를 펼친다. 즉, l_i ≤ a < b < c ≤ r_i일 때 a 번, b 번, c 번 학생이 나와 주어진 동작을 마친다.

센터가 가진 매력이 독보적일수록 무대의 매력이 증가한다. i번 학생이 가진 매력을 Ai라고 말할 때 무대의 매력을 A_b - A_a - A_c로 계산한다.

정후는 열심히 준비한 만큼 완벽한 무대가 되기를 바란다. 정후를 위해 각 동작마다 세 명을 골라 무대의 매력의 최댓값을 알려 주자.


入力

첫째 줄에 학생의 수를 나타내는 정수 N과 동작의 수를 나타내는 정수 Q가 공백으로 구분되어 주어진다. 둘째 줄에 N 개의 정수가 공백으로 구분되어 주어진다. i 번째로 주어지는 수는 i 번 학생의 매력 Ai를 나타낸다. 셋째 줄부터 Q+2째 줄까지 동작의 정보를 나타내는 세 정수가 공백으로 구분되어 주어진다. 각 행의 첫 번째 수는 동작의 종류를 의미한다. 첫 번째 종류의 동작에서는 이어 x_i와 y_i가 주어지고, 두 번째 종류의 동작에서는 이어 l_i와 r_i가 주어진다.

제한

  • 3 ≤ N ≤ 333,333

  • 1 ≤ Q ≤ 333,333

  • 1 ≤ x_i ≤ N

  • -33,333,333 ≤ A_i, y_i ≤ 33,333,333

  • 1 ≤ l_i, r_i ≤ N

  • l_i + 2 ≤ r_i

  • 주어지는 모든 수는 정수이다.

  • 두 번째 종류의 동작이 적어도 하나 주어진다.


出力

두 번째 종류의 동작이 주어질 때마다 무대의 매력의 최댓값을 한 줄에 하나씩 출력한다.


部分問題

番号 点数 条件
#13点

  • N = 3

  • Q = 1

#215点

  • 3 ≤ N ≤ 3,000

  • 1 ≤ Q ≤ 3,000

#326点

  • 초기와 각 쿼리 이후에 i < j이면 A_i ≤ A_j이다.

#456点

  • 추가 제한 조건이 없다.


例題 

7 3
5 -3 2 -9 5 3 -16
2 1 6
1 3 4
2 3 5
14
-18


出典

2022 IamCoder Qualification Test
ログインしないとコードを書けません。