네모네모 해결하기

현재 수열의 길이를 $K$, 원소의 합을 $S$라고 하자. $K=0$이면 정답은 $0$이다.

$K \ge 1$일 때, 모든 컴포넌트와 컴포넌트 사이의 필수 빈칸을 가장 조밀하게 배치하는 데 필요한 길이는

$$L=S+K-1$$

이다. 올바른 색칠이 존재하므로 $L \le W$이다. 남는 빈칸의 수를

$$D=W-L$$

이라고 하자.

$i$번째 컴포넌트를 가능한 한 왼쪽에 배치했을 때의 시작점을 $p_i$라고 하자. 가능한 한 오른쪽에 배치하면 모든 컴포넌트의 시작점이 정확히 $D$만큼 오른쪽으로 이동하므로, $i$번째 컴포넌트의 시작점은 $p_i+D$가 된다.

따라서 $i$번째 컴포넌트가 모든 올바른 색칠에서 덮는 칸은 두 배치에서의 구간이 겹치는 부분이고, 그 개수는

$$\max(0,A_i-D)$$

이다.

이 구간들 외의 칸이 항상 색칠될 수는 없다. 왼쪽 조밀 배치에서 해당 칸보다 왼쪽에서 끝나는 컴포넌트의 개수를 $j$라고 하자. 여분의 $D$칸을 $j$번째 컴포넌트와 $j+1$번째 컴포넌트 사이에 모두 넣으면, 앞의 $j$개 컴포넌트는 왼쪽 조밀 배치에 있고 나머지는 오른쪽 조밀 배치에 있다. $$과 는 각각 첫 컴포넌트 앞과 마지막 컴포넌트 뒤의 간격을 뜻한다. 이 배치에서는 해당 칸이 색칠되지 않는다.

따라서 정답은

$$\sum_{i=1}^{K}\max(0,A_i-D) = \sum_{A_i>D}A_i-D\cdot \#\{i:A_i>D\}$$

이다.

쿼리의 삽입 위치는 이 식에 영향을 주지 않는다. 필요한 정보는 현재 원소들의 개수, 합, 그리고 값별 개수뿐이다.

모든 1번 쿼리의 $X$를 미리 모아 좌표 압축한다. 압축된 값 위에 다음 두 펜윅 트리를 유지한다.

• 각 값의 현재 등장 횟수
• 각 값이 현재 만드는 합

삽입과 삭제는 두 트리의 한 위치를 갱신한다. 현재 $D$보다 큰 값들의 개수와 합은 upper_bound와 두 펜윅 트리의 접미 구간 합으로 구한다.

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