https://codeforces.com/contest/1741/problem/D
Problem - D - Codeforces
codeforces.com
풀긴 했는데 풀이가 더러워서 다시 풂
분할 정복
현재 인덱스 범위 [l, r], 현재 숫자 범위 [nl, nr]
1) l == r 이면 arr[l]이 nl과 같아야 함.
2) arr[l]이 nmid 보다 크면 왼쪽 구간과 오른쪽 구간에 대해 분할 정복 후 둘을 뒤집어야 하므로 1을 더함.
3) 작으면 똑같이 분할 정복 후 둘을 뒤집을 필요가 없으므로 0을 더함.
불가능하면 종료 조건인 l == r 에서 알아서 걸러지므로 따로 또 뭘 할 필요가 없다(왼쪽 구간과 오른쪽 구간을 정렬 후 합치기 등).
