순열 뒤집기

초기 순열에서 $A_i=i$인 위치의 개수를 $F$라 하자.

구간 $[l,r]$을 뒤집고 $s=l+r$이라 두면, 구간 안의 원래 위치 $j$에 있던 값 $A_j$는 위치 $s-j$로 이동한다. 따라서 이 값이 뒤집은 뒤 고정점이 되기 위한 필요충분조건은 $A_j=s-j$, 즉 $j+A_j=s$이다.

그러므로 구간 $[l,r]$을 뒤집은 뒤의 고정점 개수는

$$F-\#\{j:l \leq j \leq r,\ A_j=j\}+\#\{j:l \leq j \leq r,\ j+A_j=l+r\}$$

이다. 따라서 위 식에서 빼지는 양과 더해지는 양의 차이를 최대화하면 된다.

고정된 $s=l+r$에 대해 가능한 $l$의 범위는

$$\max(1,s-N) \leq l \leq \left\lfloor\frac{s-1}{2}\right\rfloor$$

이다. 또한 $j+A_j=s$인 위치 $j$가 구간 $[l,s-l]$ 안에 들어가는 조건은 $l \leq \min(j,A_j)$와 같다. 각 $s$마다 $j+A_j=s$인 위치들의 $\min(j,A_j)$ 값을 모아 정렬해 두면, 주어진 $l$에서 새로 생기는 고정점 개수는 이분 탐색으로 구할 수 있다.

기존 고정점 개수는 고정점 prefix sum으로 바로 구한다. 고정된 $s$에서 $l$을 증가시키면 새로 생기는 고정점 개수는 저장해 둔 $\min(j,A_j)$ 값을 지날 때만 감소하고, 기존 고정점 개수는 감소할 수만 있다. 따라서 최적의 $l$은 가능한 최솟값이거나, 어떤 저장된 값 $x$에 대해 $x+1$인 경우만 확인하면 충분하다.

각 위치는 정확히 하나의 $s=i+A_i$에만 들어가므로 후보 수의 총합은 $O(N)$이다. 전체 시간 복잡도는 정렬과 이분 탐색을 포함해 $O(N\log N)$이고, 메모리 복잡도는 $O(N)$이다.

Solution written by GPT5.5