Most Ordinary Existence

서브태스크 1

각 쿼리마다 남아 있는 부원의 집합을 비트마스크로 나타낸다. 모든 부원에 대해 두 조건을 직접 확인하고, 제외할 수 있는 부원을 하나씩 제외해 재귀적으로 탐색한다. 같은 비트마스크의 결과를 저장한다. 시간 복잡도의 상한은 $O(QN^2 2^N)$이고, 메모리 복잡도는 $O(2^N+N)$이다. $N,Q \leq 8$에서 충분하다.

중앙의 두 부원

현재 부원이 $2t$명이라면 위치 조건을 만족하는 부원은 현재 $t$번째와 $(t+1)$번째 부원뿐이다. 키 조건을 만족하는 부원은 남아 있는 부원을 키순으로 정렬했을 때 $t$번째와 $(t+1)$번째 부원뿐이다.

이 두 집합의 교집합 크기를 $c$라고 하자.

• $c=0$이면 아무도 제외할 수 없다.
• $c=1$이면 그 부원 한 명만 제외할 수 있다. 그 후에는 부원이 홀수 명이므로 두 조건의 중앙값이 각각 하나로 정해진다. 새 위치 중앙값은 원래 중앙의 두 위치 중 남은 위치이고, 새 키 중앙값은 원래 중앙의 두 키 순위 중 남은 순위이다. 이 둘이 같은 부원이었다면 처음 교집합 크기가 $2$였어야 하므로, 더 이상 제외할 수 없다.
• $c=2$이면 어느 부원을 먼저 제외해도 나머지 부원이 다음으로 제외된다. 두 부원을 모두 제외한 후의 상태는 선택과 무관하다.

따라서 제외 과정을 두 명씩 묶으면 분기가 사라진다. $N$이 홀수일 때에는 먼저 중앙 위치의 부원이 중앙 키 순위를 가지는지 확인한다. 그렇지 않으면 답은 $0$이고, 그렇다면 그 부원을 제외한 뒤 같은 논의를 적용한다.

층과 답의 공식

위치 또는 키 순위 $i$의 층을 $d(i)=\min(i,N+1-i)$로 정의하자. 층 번호가 클수록 중앙에 가깝다. $k$층에는 위치 와 키 순위 가 대응한다. 홀수 길이의 가장 안쪽 층에는 위치와 키 순위가 각각 하나만 있다.

$b_k$를 $k$층의 위치 중 $d(P_i) \neq d(i)$인 위치의 개수라고 하자. 안쪽 층이 모두 정상적으로 제외되었다면, 남아 있는 위치와 키 순위의 집합은 정확히 바깥쪽 층들의 합집합이다. 따라서 현재 중앙에서 제외 가능한 부원의 수는 그 층의 일치 개수로 결정된다.

$b_k>0$인 가장 큰 $k$를 찾는다. 그런 층이 없으면 모든 부원을 제외할 수 있으므로 답은 $N$이다. 그렇지 않고 $k$층이 두 부원으로 이루어져 있다면, 안쪽의 $$명을 제외한 뒤 층에서 명을 더 제외하고 멈춘다. 답은 다음과 같다.

$$N-2k+2-b_k.$$

홀수 길이의 중앙 한 명이 불일치하는 경우에도 $k=(N+1)/2$, $b_k=1$을 대입하면 $0$이 되어 같은 공식을 사용할 수 있다.

서브태스크 2

매 쿼리마다 순열을 교환한 뒤 안쪽 층부터 순서대로 확인한다. 처음 불일치하는 층에서 위 공식을 적용한다. 시간 복잡도는 $O(NQ)$, 메모리 복잡도는 $O(N)$이다.

서브태스크 3

세그먼트 트리의 $k$번째 잎에 $b_k>0$이면 $k$, 아니면 $0$을 저장한다. 내부 노드는 두 자식의 최댓값을 저장한다. 루트에서 가장 안쪽의 불일치 층을 즉시 알 수 있다.

$x,y$의 값을 교환할 때에는 두 위치의 기존 불일치 기여를 빼고, 값을 교환한 뒤 새 기여를 더한다. 영향을 받는 층은 $d(x)$와 $d(y)$뿐이다. 두 위치가 같은 층일 수 있으므로 기여를 모두 반영한 뒤 해당 잎을 갱신한다. 원래의 $N$과 층 번호는 정답 계산 중에 변하지 않는다.

초기화는 $O(N)$, 쿼리 하나는 $O(\log N)$이다. 전체 시간 복잡도는 $O(N+Q\log N)$, 메모리 복잡도는 이다.

정수 범위와 경계

입력, 층 번호, 정답은 $200\,000$ 이하이고 $b_k$는 $2$ 이하이다. 정답 식의 각 항은 절댓값이 $200\,002$ 이하이다. 세그먼트 트리의 잎 용량은 최대 $131\,072$, 배열 크기는 최대 이다. 완전탐색 풀이의 비트마스크 수는 최대 이다. 생성기의 가장 큰 곱셈은 이며, 시드 해시의 중간값은 미만이다. 검증기는 곱셈 전에 범위를 검사한다. 모든 코드의 수치는 부호 있는 비트 정수 범위 안에 있다.

제시된 조건에서 $Q \geq 1$이고 $x_q \neq y_q$이므로 인 유효한 입력은 존재하지 않는다. 생성기는 부터 생성하고, 검증기는 원래 제약을 그대로 검사한다.

Solution written by GPT6