서브태스크 1: 만남 순서를 직접 시도하기
종류 1 쿼리는 배열을 직접 갱신한다. 종류 2 쿼리의 구간 길이를 M이라 하면, 구간 안의 M−1개 만남을 처리하는 순서는 (M−1)!가지이다. 각 순서를 그대로 시뮬레이션하여 비용의 최솟값을 구할 수 있다. N,Q≤8이므로 이 완전 탐색으로 충분하다.
이 방법에서 가장 큰 병목은 만남의 순서를 모두 나열한다는 점이다. 먼저 한 번의 회의에 대한 답을 순열 없이 계산해 보자.
한 번의 회의를 순열 없이 계산하기
종류 2 쿼리의 구간을 [L,R]이라 하고, 모든 만남이 끝난 뒤 i번 연구자의 추정값을 Bi라 하자.
L<i<R인 연구자는 양쪽 이웃과 한 번씩 만난다. 추정값은 감소하지 않으므로
Bi≥max(A[i−1],A[i],A[i+1])
가 반드시 성립한다. 두 끝점에서는 각각
BL≥max(A[L],A[L+1]),BR≥max(A[R−1],A[R])
이라는 하한을 얻는다.
이 하한들은 동시에 달성할 수 있다. i번 연구자와 i+1번 연구자의 만남에 Wi=max(A[i],A[i+1])라는 값을 붙이고, Wi가 작은 만남부터 처리한다.
값이 w인 만남을 처리하는 순간을 보자. 그 전에 처리된 모든 만남의 값은 w 이하이다. 현재 두 연구자 중 한 명의 추정값이 w보다 크다면, 그 값은 어떤 초기 추정값 A[j]>w에서 전파되어 온 것이다. 그런데 이 값이 처음 다른 위치로 이동할 때 통과한 만남의 값은 적어도 A[j]여야 하므로, 그 만남이 이미 처리되었다는 것과 모순이다. 따라서 두 연구자의 현재 추정값은 모두 w 이하이다. 한편 둘 중 적어도 한 명의 초기 추정값은 w이므로, 만남 직후 두 추정값은 정확히 w가 된다.
i번 연구자가 마지막으로 참여하는 만남은 인접한 만남 중 W가 가장 큰 만남이다. 따라서 최종 추정값은 위 하한과 정확히 같아진다. 그러므로 L<R일 때 회의의 최소 비용은
max(A[L],A[L+1])+i=L+1∑R−1max(A[i−1],A[i],A[i+1])+max(A[R−1],A[R])
이다. L=R이면 만남이 없으므로 답은 A[L]이다.
서브태스크 4: 배열이 비내림차순인 경우
A[0]≤A[1]≤⋯≤A[N−1]이면 L<R인 쿼리의 답은
i=L+1∑RA[i]+A[R]
로 단순해진다. 종류 1 쿼리 뒤에도 비내림차순이라는 조건이 보장되므로, 구간 덧셈과 구간 합을 지원하는 느긋한 전파 세그먼트 트리를 사용하면 각 쿼리를 O(logN)에 처리할 수 있다.
만점 풀이: 갱신으로 달라지는 항만 관리하기
일반 배열에서는 다시 Ci=max(A[i−1],A[i],A[i+1])를 사용한다. 종류 2 쿼리 [L,R]의 답은 L<R일 때
max(A[L],A[L+1])+i=L+1∑R−1Ci+max(A[R−1],A[R])
이다.
이제 종류 1 쿼리로 A[L],A[L+1],…,A[R]에 V를 더한다고 하자.
L+1≤i≤R−1이면 Ci를 정의하는 세 원소가 모두 V만큼 증가하므로 Ci도 정확히 V만큼 증가한다. 반대로 [L−1,R+1] 밖의 Ci는 정의에 사용되는 세 원소가 하나도 바뀌지 않으므로 그대로이다. 따라서 일괄 갱신만으로 처리되지 않는 위치는 많아야 L−1, L, R, R+1의 네 곳뿐이다. 유효한 인덱스를 중복 없이 모은 뒤, 갱신된 A의 값을 읽어 Ci를 다시 계산하면 된다.
A에는 구간 덧셈과 점 조회가 필요하다. 차분 배열을 저장한 펜윅 트리를 사용하면 구간 덧셈을 두 번의 점 갱신으로 처리하고, A[i]를 누적 합으로 구할 수 있다.
C에는 구간 덧셈, 점 대입, 구간 합이 필요하다. 느긋한 전파 세그먼트 트리를 사용한다. 종류 1 쿼리마다 먼저 C[L+1…R−1]에 V를 더하고, 네 경계 후보를 새 값으로 대입한다. 종류 2 쿼리에서는 가운데 C의 합과 두 끝점의 쌍 최댓값을 더한다.
각 쿼리의 시간 복잡도는 O(logN)이고, 전체 시간 복잡도는 O((N+Q)logN)이다.
Solution written by GPT5.6
