Median 2

먼저 접두사 기록 $A$만 생각하자. 다음과 같이 $X_1,X_2,\cdots,X_N$을 정의한다.

$$X_i=\begin{cases} A_i/2 & (i\text{가 홀수}),\\ A_i-X_{i-1} & (i\text{가 짝수}). \end{cases}$$

홀수 $i$에서 $A_i$가 홀수이거나, 어떤 $X_i$가 $1$ 이상 이하가 아니라면 불가능하다.

$i=2k-1$일 때 $X_i$는 앞의 $i$개 원소의 중앙값이다. 여기에 $P_{i+1}$ 하나를 추가하면 기존 중앙값은 크기가 인 새 집합의 가운데 두 원소 중 하나로 남는다. 따라서 짝수 에서 가운데 두 원소는 정확히 과 이다.

이 사실로 각 위치 $i$에서 $P_i$가 들어갈 수 있는 구간 $C_i^A$를 얻을 수 있다. $$이면 이다. 짝수 에서 , 라 하면, 일 때 , 일 때 이다. 이면 서로 다른 두 가운데 원소가 같아지므로 불가능하다.

홀수 $i\ge 3$에서는 직전 짝수 접두사의 가운데 두 원소를 $l<u$라 하자. 새 중앙값 $X_i$는 $[l,u]$에 있어야 한다. 이면 , 이면 , 이면 이어야 한다. 따라서 는 항상 하나의 정수 구간이다.

위치에 대한 조건만으로는 충분하지 않다. $X_i$는 시점 $i$까지 실제로 등장해야 하므로 $\operatorname{pos}(X_i)\le i$이다. 또한 짝수 에서 가운데 두 원소가 라면, 과 사이의 값은 그 시점까지 하나도 등장할 수 없다. 따라서 모든 에 대해 이다. 이 조건들을 모으면 각 값 에 대해 접두사 기록이 주는 위치 구간 를 얻는다.

접두사 조건의 충분성

위 조건들은 필요조건일 뿐 아니라 충분조건이다. $i$를 증가시키며 귀납하자. 홀수 크기의 접두사에서 중앙값이 $c$이고 다음 짝수 시점의 다른 가운데 값이 $q<c$라고 하자. $q$는 deadline 조건 때문에 이미 등장했고, $q$와 사이의 모든 값은 release 조건 때문에 아직 등장하지 않았다. 따라서 는 현재 바로 아래의 원소이다. 새 값 를 추가하면 가운데 두 원소가 정확히 가 된다. 도 대칭적이다.

접미사 기록 $B$도 오른쪽에서 왼쪽으로 같은 처리를 한다. 접미사 길이 $N-i+1$의 홀짝에 따라

$$Y_i=\{\begin{array}{ll}{B}_i\mathrm{/}2& (N-i+1\text{이 홀수}),\\ B_i-Y_{i+1}& \end{array}$$