Meetings

서브태스크 1: 만남 순서를 직접 시도하기

종류 $1$ 쿼리는 배열을 직접 갱신한다. 종류 $2$ 쿼리의 구간 길이를 $M$이라 하면, 구간 안의 $M-1$개 만남을 처리하는 순서는 $(M-1)!$가지이다. 각 순서를 그대로 시뮬레이션하여 비용의 최솟값을 구할 수 있다. $N,Q \leq 8$이므로 이 완전 탐색으로 충분하다.

이 방법에서 가장 큰 병목은 만남의 순서를 모두 나열한다는 점이다. 먼저 한 번의 회의에 대한 답을 순열 없이 계산해 보자.

한 번의 회의를 순열 없이 계산하기

종류 $2$ 쿼리의 구간을 $[L,R]$이라 하고, 모든 만남이 끝난 뒤 $i$번 연구자의 추정값을 $B_i$라 하자.

$L<i<R$인 연구자는 양쪽 이웃과 한 번씩 만난다. 추정값은 감소하지 않으므로

$$B_i \geq \max(A[i-1],A[i],A[i+1])$$

가 반드시 성립한다. 두 끝점에서는 각각

$$B_L \geq \max(A[L],A[L+1]),\qquad B_R \geq \max(A[R-1],A[R])$$

이라는 하한을 얻는다.

이 하한들은 동시에 달성할 수 있다. $i$번 연구자와 $i+1$번 연구자의 만남에 $W_i=\max(A[i],A[i+1])$라는 값을 붙이고, $W_i$가 작은 만남부터 처리한다.

값이 $w$인 만남을 처리하는 순간을 보자. 그 전에 처리된 모든 만남의 값은 $w$ 이하이다. 현재 두 연구자 중 한 명의 추정값이 $w$보다 크다면, 그 값은 어떤 초기 추정값 $A[j]>w$에서 전파되어 온 것이다. 그런데 이 값이 처음 다른 위치로 이동할 때 통과한 만남의 값은 적어도 $A[j]$여야 하므로, 그 만남이 이미 처리되었다는 것과 모순이다. 따라서 두 연구자의 현재 추정값은 모두 $w$ 이하이다. 한편 둘 중 적어도 한 명의 초기 추정값은 $w$이므로, 만남 직후 두 추정값은 정확히 $w$가 된다.

$i$번 연구자가 마지막으로 참여하는 만남은 인접한 만남 중 $W$가 가장 큰 만남이다. 따라서 최종 추정값은 위 하한과 정확히 같아진다. 그러므로 $L<R$일 때 회의의 최소 비용은

$$\max(A[L],A[L+1]) +\sum_{i=L+1}^{R-1}\max(A[i-1],A[i],A[i+1]) +\max(A[R-1],A[R])$$

이다. $L=R$이면 만남이 없으므로 답은 $A[L]$이다.

서브태스크 4: 배열이 비내림차순인 경우

$A[0]\leq A[1]\leq\cdots\leq A[N-1]$이면 $L<R$인 쿼리의 답은

$$\sum_{i=L+1}^{R}A[i]+A[R]$$

로 단순해진다. 종류 $1$ 쿼리 뒤에도 비내림차순이라는 조건이 보장되므로, 구간 덧셈과 구간 합을 지원하는 느긋한 전파 세그먼트 트리를 사용하면 각 쿼리를 $O(\log N)$에 처리할 수 있다.

만점 풀이: 갱신으로 달라지는 항만 관리하기

일반 배열에서는 다시 $C_i=\max(A[i-1],A[i],A[i+1])$를 사용한다. 종류 $2$ 쿼리 $[L,R]$의 답은 $L<R$일 때

$$\max(A[L],A[L+1]) +\sum_{i=L+1}^{R-1}C_i +\max(A[R-1],A[R])$$

이다.

이제 종류 $1$ 쿼리로 $A[L],A[L+1],\ldots,A[R]$에 $V$를 더한다고 하자.

$L+1\leq i\leq R-1$이면 $C_i$를 정의하는 세 원소가 모두 $V$만큼 증가하므로 $C_i$도 정확히 $V$만큼 증가한다. 반대로 $[L-1,R+1]$ 밖의 $C_i$는 정의에 사용되는 세 원소가 하나도 바뀌지 않으므로 그대로이다. 따라서 일괄 갱신만으로 처리되지 않는 위치는 많아야 $L-1,\ L,\ R,\ R+1$의 네 곳뿐이다. 유효한 인덱스를 중복 없이 모은 뒤, 갱신된 $A$의 값을 읽어 $C_i$를 다시 계산하면 된다.

$A$에는 구간 덧셈과 점 조회가 필요하다. 차분 배열을 저장한 펜윅 트리를 사용하면 구간 덧셈을 두 번의 점 갱신으로 처리하고, $A[i]$를 누적 합으로 구할 수 있다.

$C$에는 구간 덧셈, 점 대입, 구간 합이 필요하다. 느긋한 전파 세그먼트 트리를 사용한다. 종류 $1$ 쿼리마다 먼저 $C[L+1\ldots R-1]$에 $V$를 더하고, 네 경계 후보를 새 값으로 대입한다. 종류 $2$ 쿼리에서는 가운데 $C$의 합과 두 끝점의 쌍 최댓값을 더한다.

각 쿼리의 시간 복잡도는 $O(\log N)$이고, 전체 시간 복잡도는 $O((N+Q)\log N)$이다.

Solution written by GPT5.6