문제 요약:
수열의 인접한 원소의 차이가 k이하이면 swap할 수 있다.
위 연산을 마음껏 사용했을 때 얻을 수 있는 lexicoographically smallest 수열은?
뇌절해서 풀긴했는데, 풀어서 기부니가 좋았다.
일단 기본 아이디어는 빨리 나왔는데, 이걸 어렵게 구현해버린거 같다. 나중에 정해도 공부할 생각.
우선 사전순으로 빨른 걸 구하라고 했을 때 아이디어는, 가장 빠른걸 고른다는 그리디를 생각해 볼 수 있다.
즉 우리는 현재 상태에서 맨 왼쪽으로 옮길 수 있는 가장 작은 value를 뽑아와야 된다는 생각을 할 수 있다.
그런데 어떤 ai가 있을때 j<i인 aj에 대해서 |aj-ai|>k라면, ai는 가장 왼쪽 원소가 될 수 없다.(자명하게도)
그리고 모든 j<i 인 j에 대해서, |aj-ai|<=k라면 가장 인접한 원소를 하나씩 swap해나가면 ai를 가장 왼쪽 원소로 옮길 수 있다.
따라서 어떤 i번째 원소 ai를 맨 앞으로 옮길 수 있다는 사실과, j<i인 모든 j에 대해서 |aj-ai|<=k와 동치이다.
이를 이용해서 풀것인데, 우리는 sweeping을 하면서 모든 i에 대해, j<i이면서 |aj-ai|>k인 j들의 수를 저장할 것이다. 그리고 만약 그 값이 0개라면 pq에 넣을 것이고,(작은 것 부터 뽑는 우선순위큐) 아니라면 일단은 그 값을 cnt라는 배열에 기록해 둘 것이다.
그리고 기본적인 아이디어는, pq에서 값을 뽑으면서, 그 뒤에있는 모든 |aj-ai|>k가 되는 쌍들의 cnt값을 빼준다는 아이디어를 사용할 것인데, 이게 좀 어렵다. 뒤에 있는 것만 빼주는게 어렵다. 그런데 잘 생각해보면, 지금 pq에 들어가 있다는 소리는 자기 앞에는 차이가 k보다 큰 쌍이 없다는 소리이므로, 뒤에 적용시켜주는것과 전체에 적용시켜주는 것은 동일하다. 따라서 레이지 세그를 이용해서 0~val-k val+k~max 까지 1빼주는 구간 업데이트 쿼리를 날린다.
그리고, 여기서 min 쿼리를 또 날려서 만약 0이라면 pq에 넣어주고, 아니라면 무시하는 식으로 풀어주면 된다.
시간복잡도는 엄청 높을거 같은데 사실은 O(nlogn)이다.
근데 상수가 클줄 알았는데 넉넉히 통과에서 사실은 놀랐다.