시간 제한메모리 제한제출정답맞힌 사람정답 비율
6 초 2048 MB322100.000%

문제

$0$번 관측탑부터 $N-1$번 관측탑까지 $N$개의 관측탑이 순서대로 설치되어 있다. $0 \le i \le N-1$에 대해 $i$번 관측탑의 높이는 $H[i]$이다. 또한 각 관측탑은 관측 점수 $S[i]$를 가지며, 초기에는 모든 관측 점수는 $0$이다.

$0 \le i < j \le N-1$를 만족하는 $i, j$에 대해, $i$번 관측탑에서 $j$번 관측탑이 관측 가능하다는 것은 모든 $i \le k \le j-1$에 대해 $H[k] < H[j]$임을 의미한다. $j \le i$인 관측탑들은 관측 가능하지 않음에 유의하라.

어떤 관측탑에서 관측을 진행하면, 해당 관측탑에서 관측 가능한 모든 관측탑의 관측 점수가 $1$ 증가한다.

이제 $Q$개의 이벤트가 일어난다. 각 이벤트는 다음 세 가지 종류 중 하나이다.

  • 관측: $0 \le I \le N-2$를 만족하는 $I$에 대해, $I$번 관측탑에서 관측을 진행한다.
  • 측정: $0 \le L \le R \le N-1$를 만족하는 $L$과 $R$에 대해, $L$번 관측탑부터 $R$번 관측탑까지의 관측 점수의 합을 구한다. 즉, $S[L] + \cdots + S[R]$를 구한다.
  • 지각 변동: $0 \le L \le R \le N-1$를 만족하는 $L, R$ 및 값 $V$에 대해, $L$번 관측탑부터 $R$번 관측탑까지의 각 관측탑의 높이가 $V$만큼 변한다. 즉, $H[L], \ldots, H[R]$의 값에 $V$가 더해진다.

관측 이벤트는 배열 $[I]$로, 측정 이벤트는 배열 $[L, R]$로, 지각 변동 이벤트는 배열 $[L, R, V]$로 표현할 수 있다. 이벤트의 종류마다 배열의 크기가 다르기에 배열의 크기를 기준으로 어떤 이벤트인지 구분할 수 있음에 유의하라.

이벤트들은 $0$번 이벤트부터 $Q-1$번 이벤트까지 순서대로 일어나며, $i$번 이벤트는 $E[i]$이다.

총 측정 이벤트의 개수를 $K$라 하자. 각 측정 이벤트를 일어난 순서대로 $0$번 측정 이벤트부터 $K-1$번 측정 이벤트라고 하자. 모든 측정 이벤트의 결과값, 즉 $0$번 측정 이벤트부터 $K-1$번 측정 이벤트의 결과값을 모두 구해야 한다.

함수 목록 및 정의

다음 함수를 구현해야 한다.

vector<long long> tower_events(vector<int> H, vector<vector<int>> E)
  • $H$: 크기가 $N$인 정수 배열.
  • $E$: 크기가 $Q$인 배열들의 배열. 각 값은 이벤트를 나타내는 배열이다.
  • 이 함수는 크기가 $K$인 정수 배열 $X$를 반환해야 한다. $X[i]$는 $i$번 측정 이벤트의 결과값이어야 한다. ($0 \le i \le K-1$)
  • 이 함수는 단 한 번만 호출된다.

제한

  • $5 \le N \le 1\,000\,000$
  • $1 \le Q \le 250\,000$
  • $1 \le H[i] \le 10^9$ ($0 \le i \le N-1$)
  • 각 관측 이벤트에 대해 $0 \le I \le N-2$
  • 각 측정 이벤트에 대해 $0 \le L \le R \le N-1$
  • 각 지각 변동 이벤트에 대해 $0 \le L \le R \le N-1$
  • 각 지각 변동 이벤트에 대해 $-10^9 \le V \le 10^9$
  • 각 지각 변동 이벤트 후, 모든 관측탑의 높이는 $1$ 이상이다. 즉, $1 \le H[i]$ $(0 \le i \le N-1)$
  • 측정 이벤트는 최소 한 번 일어난다.

서브태스크

번호배점제한
117

$N, Q \le 150\,000$. 모든 측정 이벤트에서 $L = 0$, $R = N-1$이다.

26

$N, Q \le 150\,000$. 지각 변동 이벤트가 일어나지 않는다.

312

$N, Q \le 150\,000$.

419

모든 관측 이벤트에서 $I = 0$이다. 모든 지각 변동 이벤트에서 $L = R$이다. 지각 변동 이벤트는 최대 $30\,000$번 일어난다.

521

모든 측정 이벤트에서 $L = R$이다. 모든 지각 변동 이벤트에서 $L = R$이며 $V \ge 0$이다.

625

추가적인 제약조건이 없다.

예제

예제 1

다음 호출을 생각해보자:

tower_events([1, 2, 3, 4, 5], [[0], [1, 3], [1, 2, 1], [1], [0, 4]])
  • 첫 번째 이벤트 이후 $H = [1,2,3,4,5]$, $S = [0,1,1,1,1]$이다.
  • 두 번째 이벤트인 $0$번 측정 이벤트의 결과값은 $S[1] + S[2] + S[3] = 3$이다.
  • 세 번째 이벤트 이후 $H = [1,3,4,4,5]$, $S = [0,1,1,1,1]$이다.
  • 네 번째 이벤트 이후 $H = [1,3,4,4,5]$, $S = [0,1,2,1,2]$이다.
  • 마지막 이벤트인 $1$번 측정 이벤트의 결과값은 $S[0] + \cdots + S[4] = 6$이다.

따라서 함수는 $[3,6]$을 반환해야 한다.

예제 2

다음 호출을 생각해보자:

tower_events([7, 7, 9, 5, 8, 10, 2, 9, 2, 2], [[1], [6, 8, 6], [1], [1, 9], [3], [8], [2, 4], [5], [1, 1, 7], [1], [0, 9]])

함수는 $[5, 3, 10]$을 반환해야 한다.

샘플 그레이더

샘플 그레이더의 입력 형식은 다음과 같다.

  • line $1$: $N$ $Q$
  • line $2$: $H[0]$ $H[1]$ $\cdots$ $H[N-1]$
  • 모든 $0 \le i \le Q-1$에 대해:
    • line $3+i$: $|E[i]|$ $E[i][0]$ $\cdots$ $E[i][|E[i]|-1]$

샘플 그레이더는 다음 형식으로 답을 출력한다:

  • 모든 $0 \le i \le K-1$에 대해:
    • line $1+i$: $X[i]$

첨부

제출할 수 있는 언어

C++17, C++20, C++23, C++26, C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.