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