Segment Tree 연습문제 1

길이가 n인 수열 \(a_0, a_1, \cdots, a_{n-1}\) \((0 ≤ a_i ≤ 10^9)\) 에서 아래 두 가지 쿼리를 처리하는 프로그램을 작성하라

- 0 i x : ai 를 x로 바꾼다. (\(0 ≤ i ≤ n - 1, 0 ≤ x ≤ 10^9\))

- 1 l r : \(\max(a_l, a_{l+1}, \cdots , a_{r-1}) - \min(a_l, a_{l+1}, \cdots , a_{r-1})\)를 출력한다. (0 ≤ l < r ≤ n)

[입력]
첫 번째 줄에 테스트 케이스의 수 T 가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 배열의 길이 n(1 ≤ n ≤ \(10^5\))과 쿼리의 개수 q(1 ≤ q ≤ \(10^5\))가 주어진다.
두 번째 줄에는 배열 a가 주어진다.
세 번째 줄부터 q개 줄에 걸쳐 쿼리가 주어진다.

[출력]
각 테스트 케이스마다 1번 쿼리의 결과를 공백으로 구분하여 출력한다.

입력

출력

#1 4 2 8 7  
#2 10 0