5257 : A58 - RMQ (Range Maximum Queries)
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
길이가 $N$ 인 수열 $A = (A_1, A_2, \ldots, A_N) $ 이 있으며, 처음에는 모든 요소가 0입니다. 다음 2종류의 쿼리를 처리하세요.
쿼리의 수는 총 $Q$ 개입니다.
[제약 조건]
• 입력되는 모든 값은 정수입니다.입니다.
• $1 \le N \le 100000$
• $1 \le Q \le 100000$
• $1 \le \mathrm{pos} \le N$
• $0 \le x \le 10^9$
• $1 \le l < r \le N + 1$
- 쿼리 1: $A_{pos}$ 의 값을 $x$ 로 갱신한다.
- 쿼리 2: $A_l, A_{l+1}, \ldots, A_{r-1}$ 의 최댓값을 답한다.
쿼리의 수는 총 $Q$ 개입니다.
[제약 조건]
• 입력되는 모든 값은 정수입니다.입니다.
• $1 \le N \le 100000$
• $1 \le Q \le 100000$
• $1 \le \mathrm{pos} \le N$
• $0 \le x \le 10^9$
• $1 \le l < r \le N + 1$
입력 설명
첫째 줄에 $N, Q$ 가 주어집니다.
둘째 줄부터 $Q$ 개의 줄에 걸쳐 쿼리가 주어집니다.
둘째 줄부터 $Q$ 개의 줄에 걸쳐 쿼리가 주어집니다.
출력 설명
각 쿼리 2에 대한 결과를 출력하세요.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
8 4
1 3 16
2 4 7
1 5 13
2 4 7
출력 예시
COPY
복사되었습니다!
복사되었습니다!
0
13