길이가 n인 배열 A₁, A₂, ..., A_x, ..., A_n이 있다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

1 x c: x의 오른쪽에 있는 c보다 큰 수들 중, 가장 왼쪽에 있는 수의 위치를 출력한다. 없다면 -1을 출력한다.

2 x c: x의 왼쪽에 있는 c보다 큰 수들 중, 가장 오른쪽에 있는 수의 위치를 출력한다. 없다면 -1을 출력한다.

3 x c: A_x를 c로 바꾼다.

이 문제는 Segment Tree만을 사용하여 푸는 것을 목표로 한다. 되도록이면 쿼리당 O(lg n)에 풀 수 있도록 해보자.

배열과 쿼리 2 timer 5s memory 512MB

배열과 쿼리 2 5s 512MB