MEX 점수 구하기

구간 $I=[l,r]$의 MEX와 같은 MEX를 갖는 더 작은 비어 있지 않은 부분 구간이 없다면 $I$를 극소 MEX 구간이라고 하자. 모든 길이 $1$ 구간은 극소 MEX 구간이다.

$C_i$는 모두 음이 아니다. 임의의 구간에서 MEX를 바꾸지 않는 끝점을 지우면 비용 합은 증가하지 않는다. 이 과정을 반복하면 같은 MEX를 갖는 극소 MEX 구간을 얻고, 점수는 감소하지 않는다. 따라서 답의 후보는 극소 MEX 구간만 보면 충분하다.

길이가 $2$ 이상인 극소 MEX 구간 $[l,r]$에서는 $A_l\ne A_r$이다.

$A_l<A_r$인 경우를 보자. 오른쪽 끝점을 지우면 MEX가 바뀌므로

$$\operatorname{mex}(A_l,\cdots,A_r)>A_r$$

이어야 한다. 오른쪽 끝점 $r$을 고정하면 이 조건을 만족하는 가장 큰 $l$은 유일하다. $r$까지 각 값 $x$가 마지막으로 등장한 위치를 $\operatorname{last}_r(x)$라 하면

$$l=\min_{0\le x\le A_r}\operatorname{last}_r(x)$$

이다. 모든 값이 실제로 등장했고, $A_r$의 직전 등장 위치가 $l$보다 작을 때만 $r$을 지우면 MEX가 바뀐다. 이 조건을 만족하면 극소 구간 하나를 얻는다.

$A_l>A_r$인 경우는 대칭적이다. $l$부터 각 값 $x$가 처음 등장하는 위치를 $\operatorname{next}_l(x)$라 하면

$$r=\max_{0\le x\le A_l}\operatorname{next}_l(x)$$

으로 후보를 구할 수 있다. $A_l$의 다음 등장 위치가 $r$보다 커야 한다.

첫 번째 경우에는 각 $r$마다 후보가 최대 하나이고, 두 번째 경우에는 각 $l$마다 후보가 최대 하나이다. 길이 $1$ 구간까지 합쳐도 후보 수는 $O(N)$이다.

왼쪽에서 스캔할 때 값 축 $0,1,\cdots,N$ 위에 마지막 등장 위치를 저장하는 세그먼트 트리를 사용한다. 다음 연산이 필요하다.

• 구간 $[0,x]$의 최솟값.
• 저장된 위치가 기준 $l$보다 작은 가장 작은 값. 이것이 구간의 MEX이다.

오른쪽에서 스캔할 때는 다음 등장 위치의 최댓값과, 저장된 위치가 기준 $r$보다 큰 가장 작은 값을 같은 방법으로 구한다. 극소 구간 전체를 $O(N\log N)$에 구할 수 있다.

각 후보 $[s,e]$의 가중치는

$$w(s,e)=B_{\operatorname{mex}(A_s,\cdots,A_e)}-(P_e-P_{s-1})$$

이다. 여기서 $P$는 $C$의 누적 합이다.

질의를 오른쪽 끝점 $r$의 오름차순으로 정렬한다. 후보도 $e$의 오름차순으로 정렬하고, 현재 질의의 $r$ 이하인 후보를 모두 추가한다. 시작점 $s$ 위치에 후보 가중치의 최댓값을 저장하는 세그먼트 트리를 두면, 질의 $[l,r]$의 답은 시작점 구간 $[l,N]$의 최댓값이다. 추가된 후보는 이미 $e\le r$을 만족하므로 정확히 $[l,r]$ 안에 포함되는 후보만 선택된다.

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