플래티넘 IV설명
\(N\)개의 정수로 이루어진 배열 \(a\)를 다음 연산에 대해 관리하여라.
- \(1\ i\ x\) — \(a[i] = x\)로 설정한다.
- \(2\ l\ r\ v\) — \(l \le j \le r\)이고 \(a[j] \ge v\)인 가장 작은 인덱스 \(j\)를 출력하고, 그러한 인덱스가 없으면 \(-1\)을 출력한다.
최댓값 세그먼트 트리 위에서의 O(log N) 하강(descent)으로 각 질의에 답할 수 있다. 저장된 최댓값이 \(v\) 이상인 자식으로만 내려가되, 왼쪽 자식을 우선한다.
제약
- \(1 \le N, Q \le 200000\)
- \(-10^9 \le a[i], x, v \le 10^9\)
입력 형식
첫째 줄에 \(N\ Q\); 둘째 줄에 \(N\)개의 정수; 그 뒤로 \(Q\)개의 연산 줄이 주어진다.
출력 형식
2번 연산마다 조건을 만족하는 가장 작은 인덱스(1-인덱스)를 출력하고, 없으면 \(-1\)을 출력한다.
예제 1
입력
6 3
3 1 4 1 5 9
2 1 6 4
1 3 2
2 1 6 4출력
3
5설명
First index with value ≥ 4 is index 3 (value 4). After a[3]=2, the first value ≥ 4 is index 5 (value 5).
문제 정보
riseoj 작성
출처 Original
태그
