\(N\)개의 정수로 이루어진 배열 \(a\)를 다음 연산에 대해 관리하여라.

1. \(1\ i\ x\) — \(a[i] = x\)로 설정한다.
2. \(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\)을 출력한다.

riseoj 작성

출처 Original