바이러스 시뮬레이터

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

요약
면역력을 소모하며 뒤쪽의 더 높은 면역력 보유자로 전이되는 바이러스 침투, 백신 접종, 구간 그룹 합 최댓값 질의를 처리한다.
난이도

어려움10점 중 8점

유형
세그먼트 트리, 이분 탐색, 시뮬레이션, 누적 합
정답자
아직 제출이 없습니다

문제

2123년 봄, 드디어 '바이러스 시뮬레이터'가 출시되었다.

바이러스 시뮬레이터는 사람들의 면역력과 바이러스의 생명력 등을 설정하여 직접 시뮬레이션을 진행하는 프로그램으로, 훗날 바이러스가 창궐할 때를 대비하여 만든 프로그램이다.

이 시뮬레이터에는 초기에 NN명의 사람들이 11번부터 NN번까지 번호 순서대로 배치되어 있고, ii번째 사람의 면역력은 A_iA\_i이다.

여기에 한 번 이상의 행동을 할 수 있으며, 행동의 종류는 바이러스 침투, 백신 접종, 그룹 면역력 측정 총 3가지가 있다. 각 행동은 입력으로 아래와 같이 주어진다.

  • 11 ii xx: 바이러스 침투 - 생명력이 xx인 바이러스가 ii번 사람에게 침투한다. 바이러스는 생명력을 11만큼 소모하여 감염자의 면역력을 11 감소시킨다. 이때 침투한 바이러스가 죽기 전에 감염자의 면역력이 없거나(즉, 면역력이 00이거나) 없어지게 된다면, 바이러스는 현재 위치한 감염자의 번호보다 큰 번호를 가진 사람 중 가장 면역력이 높은 사람에게 전이되며, 생명력이 00이 되어 죽거나 더 이상 전이될 사람이 없을 때까지 반복된다. 전이 조건과 일치하는 사람이 여러 명일 경우, 그중 번호가 가장 작은 사람에게 전이된다. (1≤i≤N;1≤x≤109)(1 \le i \le N;1 \le x \le 10^{9})
  • 22 ii xx: 백신 접종 - ii번 사람에게 효력이 xx인 백신을 접종하여 면역력이 xx만큼 오른다. (1≤i≤N;1≤x≤109)(1 \le i \le N;1 \le x \le 10^{9})
  • 33 ll rr: 그룹 면역력 측정 - ll번부터 rr번까지의 사람들이 그룹을 형성한다. 그룹은 인접한 사람들끼리 구성할 수 있고, 면역력이 없는 사람들은 없는 사람들끼리, 있는 사람들은 있는 사람들끼리 그룹을 만든다. 이때 구성되는 그룹 중, 그룹 구성원의 면역력의 합의 최댓값을 구한다. (1≤l≤r≤N)(1 \le l \le r \le N)

사람의 수 NN과 QQ번의 행동 목록이 주어지면, 시뮬레이터를 실행했을 때의 결과를 직접 출력해 보자.

행동은 행동 목록 순서대로 수행되며, 한 번의 행동이 완료될 때까지 그 다음 행동이 수행되지 않는다.

입력

첫 번째 줄에 사람들의 수 NN과 행동의 횟수 QQ를 나타내는 두 정수가 공백을 사이에 두고 주어진다. (1≤N,Q≤200,000)(1 \le N, Q \le 200\\,000)

두 번째 줄에 각 사람의 면역력을 나타내는 NN개의 정수 A_iA\_i가 공백을 사이에 두고 주어진다. (1≤A_i≤109)(1 \le A\_i \le 10^{9})

세 번째 줄부터 QQ개의 줄에 걸쳐 행동 목록이 주어진다.

그룹 면역력 측정 행동이 최소 한 번 이상 주어진다.

출력

그룹 면역력 측정 행동이 주어질 때마다, 그 결과를 한 줄에 하나씩 출력한다.

예제2

  1. 예제 1

    입력
    10 7
3 5 2 6 4 7 2 9 3 5
3 1 6
1 3 8
3 1 6
1 5 18
3 3 8
2 6 1
3 3 8
    예상 출력
    27
17
6
6

  2. 예제 2

    입력
    9 8
6 3 5 2 3 1 2 3 2
1 2 10
1 2 5
1 3 2
3 2 8
1 7 2
2 4 10
1 3 6
3 2 9
    예상 출력
    4
6