소팅할 때마다 해당 데이터를 버린다고 생각해보세요.
1. 소팅할 때 고른 수 k는 소팅이 되지 않은 데이터 중에서 가장 작은 수이거나 가장 큰 수이다.
2-1. k가 가장 작은 수
k가 가장 작다면 k를 반드시 맨 왼쪽에 배치해야 합니다. 그러면 k보다 작은 위치에 있으면서 큰 수의 개수를 구하면 됩니다.
2-2. k가 가장 큰수
k가 가장 크다면 k를 반드시 맨 오른쪽에 배치해야 합니다. 그러면 k보다 큰 위치에 있으면서 작은 수의 개수를 구하면 됩니다.
"남아 있는 수들"에 대해서 확인을 해야 하므로
세그 트리에 사용한 위치를 0으로 바꿔서 제거하는 동작을, 구간합을 구하도록 구성하면 이는 곧 인덱스 위치에 대한 남아있는 수를 가져오는 것이므로 2-1, 2-2 모두 처리할 수 있는거죠.
yoonfy4280 4년 전
아래 질문 게시판에 있는 풀이를 참고하여 어렵게 어렵게 이해가 안되 풀었습니다.
그 사용한 위치는 0으로 바꾸고 구분 합 -1 을 답으로 처리해줬는데, 저는 이 문제를 1을 뽑아서 맨 앞에 두는데 거쳐가는 1의 수를 출력했고
가장 숫자가 높은 N은 마지막 위치에 두는데 거쳐가는 1의 수를 출력는 걸로 이해했습니다.
그런데 이 문제에서 앞의 숫자와 바꿔간다라는 말이 있는데, 숫자의 위치를 바꾸지 않고 어떻게 1의 개수의 합이 답이 되는지 이해가 아직 안됩니다....
알려주세요 ㅠㅠ.