문제
길이가 n인 배열 A1, A2, ..., Ax, ..., An이 있다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.
1 x c: x의 오른쪽에 있는 c보다 큰 수들 중, 가장 왼쪽에 있는 수의 위치를 출력한다. 없다면 -1을 출력한다.
2 x c: x의 왼쪽에 있는 c보다 큰 수들 중, 가장 오른쪽에 있는 수의 위치를 출력한다. 없다면 -1을 출력한다.
3 x c: Ax를 c로 바꾼다.
이 문제는 Segment Tree만을 사용하여 푸는 것을 목표로 한다. 되도록이면 쿼리당 O(lg n)에 풀 수 있도록 해보자.
입력
첫째 줄에 배열의 크기 n과 쿼리의 개수 q (1 ≤ n, q ≤ 500,000)가 주어진다.
둘째 줄에는 A1, A2, ..., An이 주어진다. (-109 ≤ Ai ≤ 109)
다음 q개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. (1 ≤ x ≤ n, -109 ≤ c ≤ 109)
출력
1, 2번 쿼리가 주어질 때 마다 정답을 한 줄에 하나씩 출력한다.
예제
10 10
5 2 2 1 2 2 2 2 3 4
3 6 0
3 10 0
1 9 0
2 3 1
1 1 4
1 2 0
2 7 1
3 4 3
3 10 4
1 2 1
-1
2
-1
3
5
3
로그인해야 코드를 작성할 수 있어요.