리더 찾기

사람을 고르는 경우와 삽입 위치를 모두 열거하면 $O(N^2)$개 이동을 확인해야 한다. $N\le200\,000$이므로 한 사람을 빼는 영향과 다시 넣는 위치를 분리해서 생각한다.

한 사람을 빼면 새 리더가 되는 경우

리더가 아니라는 것은 왼쪽에 자신보다 작은 사람이 있고, 오른쪽에 자신보다 큰 사람도 있다는 뜻이다. 한 사람을 빼는 것으로 기존의 다른 리더가 자격을 잃지는 않는다.

현재 리더가 아닌 $i$가 $j$를 뺀 뒤 리더가 되려면, $j$가 $i$의 왼쪽에서 자신보다 작은 유일한 사람이거나 오른쪽에서 자신보다 큰 유일한 사람이어야 한다. 둘 중 하나의 방해가 완전히 사라져야 하기 때문이다.

각 사람 $j$에 대해 이 조건으로 새 리더가 되는 사람 수를 $g_j$에 센다. 같은 $i$의 두 방해자는 서로 다른 쪽에 있으므로 하나의 $g_j$에 중복해서 더해지지 않는다.

새 리더를 유지하며 다시 넣을 수 있다

빼낸 능력치 $x$를 남은 줄에서 $x$보다 작은 첫 사람 바로 앞에 넣는다. 그런 사람이 없으면 맨 뒤에 넣는다. $x$의 앞에는 $x$ 이상인 사람만 있으므로 움직인 사람은 리더가 된다.

삽입 위치 앞의 사람은 능력치가 $x$ 이상이므로 오른쪽에 $x$가 생겨도 오른쪽 조건을 잃지 않는다. 삽입 위치 뒤의 사람은 능력치가 $x$ 이하라면 왼쪽 조건을 잃지 않는다. $x$보다 큰 사람은 이미 앞에 $x$보다 작은 사람이 있었으므로 원래도 왼쪽 조건으로 리더가 될 수 없었다. 이 사람들의 오른쪽 조건은 바뀌지 않는다.

따라서 빼낸 직후의 모든 리더를 유지하면서 움직인 사람도 리더로 만들 수 있다.

유일한 방해자를 선형 시간에 찾기

접두사 최솟값과 접미사 최댓값으로 기존 리더 여부를 구한다. 이어서 각 위치의 왼쪽 부분에 있는 가장 작은 두 원소와 최솟값의 위치, 오른쪽 부분에 있는 가장 큰 두 원소와 최댓값의 위치를 전처리한다. 두 원소는 서로 다른 값이 아니라 중복을 포함한 두 위치를 뜻한다.

리더가 아닌 $i$에 대해 왼쪽의 두 최솟값을 $m_1\le m_2$라 하면 $m_1<A_i\le m_2$일 때만 최솟값의 위치가 유일한 작은 방해자이다. 오른쪽의 두 최댓값을 $M_1\ge M_2$라 하면 $M_1>A_i\ge M_2$일 때만 최댓값의 위치가 유일한 큰 방해자이다. 해당 위치의 $g$를 $1$ 늘린다. 두 번째 원소가 없다면 각각 양의 무한대와 음의 무한대를 쓴다.

원래 리더 수를 $C$, $j$의 기존 리더 여부를 $I_j\in\{0,1\}$라 하면 $j$를 움직여 얻는 최댓값은
\[ C+g_j+1-I_j \]
이다. 제거 직후의 리더 수가 상한이고 위 삽입법이 이를 달성하므로, 모든 $j$에 대해 이 식의 최댓값을 출력한다.

시간복잡도와 공간복잡도는 $O(N)$이다. $N=1$에서도 같은 식으로 $1$을 얻는다.