https://www.acmicpc.net/problem/16909




문제 안읽으신분들을 위한 설명: 5 13 8 10 7 3 10 9 4 10 20 17 이라는 배열이 있으면 내가 지금 이 수열에서 7번째에 위치한 10이라는 수를 검사한다고 생각하면, 좌우로 각각 10보다 작고 7번째라는 인덱스에서 제일 먼 수의 인덱스를 알고싶은데 이 방법을 잘 모르겠어요 위 예제에서는 5와 9입니다.


세그먼트 트리로 할 수 있을것 같은데 다른 블로그 보니까 유니온파인드를 사용하는 아이디어가 있던데 그게 최적해를 보장하는지 모르겠어요. 혹시 설명해주실수 있는 분 계신가요? 질문이 길어서 죄송합니다 ㅜㅜ