두 수열의 S의 기우성이 같다면 "기술"을 적당히 사용하여 한 수열을 다른 수열로 바꿀 수 있습니다.
증명)
보조정리 1) "기술"을 3번 사용하면 원래 상태로 돌아온다.
보조정리 2) "기술"을 사용해도 S의 기우성이 바뀌지 않는다.
보조정리 3) "기술"을 사용해서 ${A_1, ...., A_{n-2}}$가 오름차순 정렬돼있게 할 수 있다.
두 수열의 S의 기우성이 다르면 불가능함은 자명하다.
${A_1, ...., A_{n-2}}$와 ${B_1, ...., B_{n-2}}$가 오름차순 정렬돼있으면 S는 0 혹은 1이다. 즉 S의 기우성이 같다면, 두 정렬된 수열은 같아진다. 보조정리 1에 의해 항상 원래 상태로 돌아갈 수 있으므로, 수열 A의 앞의 n-2개를 정렬하고, B를 정렬한 역변환을 해주면 A에서 B로 바꿀 수 있다.
S는 C. 달리기와 같은 방법으로 구할 수 있습니다. 오버플로우가 나지 않도록 long long을 사용합시다.
i번째 전함이 포함하는 x 구간 [sx_i, ex_i]와 y 구간 [sy_i, ey_i]를 정의합니다.
만약 x = p라는 대포를 쏜다면, x 구간이 p를 포함하는 전함을 모두 탐색하여 무게의 최댓값을 구하고, 그 전함들을 모두 제거하는 풀이를 생각해볼 수 있습니다. 각 전함을 1~2번 정도만 본다면 아주 빠르게 문제를 해결할 수 있기 때문입니다.
전함의 sx를 기준으로 오름차순 정렬을 해줍니다. 세그먼트 트리를 초기화해주는데, sx로 정렬된 순서로 ex를 세그먼트 트리에 넣어줍니다. 세그먼트 트리는 최솟값은 저장하는 세그먼트 트리입니다.
x = p라는 대포를 쏘았을 때, sx가 p이하이고 ex가 p 이상이 되는 전함들이 파괴됩니다.
이분탐색을 써서 sx가 p 이하가 되는 최대의 인덱스 x를 구할 수 있습니다.
그러면 세그먼트 트리의 1 ~ x 구간에서 ex가 p 이상인 것들을 찾는 문제로 바뀝니다. 세그먼트 트리를 써서, 구간의 ex의 최댓값이 p보다 작으면 더 이상 탐색하지 않습니다. 그 구간에는 ex가 p 이상인 전함들이 단 한개도 존재하지 않기 때문입니다. 세그트리의 리프 노드까지 내려왔을 때, 전함의 무게를 체크해준 후 그 전함의 ex를 음의 무한대로 수정해줍니다. 그렇게 한다면 전함 1개당 $O(log(n))$만큼 계산이 필요하므로, 아무리 오래 걸려도 총 $O(n log(n))$이 소요됩니다.
주의할 점은 y = q 꼴의 대포에 의해 전함이 파괴됐을 때 x = p 대포가 갱신되지 않았다는 점인데, 이 경우는 전함의 파괴여부를 확인하는 배열 vt를 만들어서, 다른 축에서 파괴된 전함은 무게의 최댓값을 구할 때 계산에서 제외해주면 됩니다.