문제 70
첫 번째 큰 수
길이가 $N$인 정수 수열 $A_1, A_2, \cdots, A_N$이 있다. $Q$개의 쿼리를 순서대로 처리하라.
쿼리는 다음 중 하나이다.
1 i x: $A_i$를 $x$로 바꾼다.2 l r x: $l \le i \le r$이면서 $A_i \ge x$인 가장 작은 $i$를 출력한다. 조건을 만족하는 $i$가 없다면-1을 출력한다.
입력
첫 번째 줄에 두 정수 $N$, $Q$가 공백으로 구분되어 주어진다. $(1 \le N, Q \le 200\,000)$
두 번째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(-10^9 \le A_i \le 10^9)$
세 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 하나씩 주어진다.
각 쿼리는 1 i x 또는 2 l r x 형식으로 주어지며, 각 값은 공백으로 구분되어 주어진다. 1 i x에서는 $(1 \le i \le N; -10^9 \le x \le 10^9)$, 2 l r x에서는 $(1 \le l \le r \le N; -10^9 \le x \le 10^9)$이다.
출력
2 l r x 쿼리마다 조건을 만족하는 가장 작은 인덱스를 한 줄에 하나씩 출력한다. 조건을 만족하는 인덱스가 없다면 -1을 출력한다.
예제 입력 1
6 7 1 5 2 8 3 7 2 1 6 6 2 2 5 9 1 3 10 2 2 5 9 1 4 -1 2 1 6 6 2 4 6 6
예제 출력 1
4 -1 3 3 6
공식 해설
어떤 구간의 최댓값이 $x$보다 작다면 그 안에는 찾는 원소가 없다. 구간 최댓값 세그먼트 트리를 만들어 이 조건으로 탐색할 필요가 없는 구간을 건너뛴다.
점 갱신은 해당 리프를 바꾸고 조상들의 최댓값을 다시 계산하면 된다. 질의에서는 루트부터 다음 규칙으로 내려간다.
현재 구간이 $[l,r]$과 겹치지 않거나 저장한 최댓값이 $x$보다 작으면 실패로 처리한다. 리프까지 도착했다면 그 위치가 답이다. 그 밖에는 왼쪽 자식을 먼저 탐색하고, 왼쪽에서 찾지 못했을 때만 오른쪽을 탐색한다.
왼쪽에서 답이 없음을 확인한 뒤에만 오른쪽으로 가므로 처음 찾은 위치가 조건을 만족하는 가장 작은 인덱스이다. 끝까지 찾지 못하면 $-1$을 출력한다.
질의 구간을 나누는 $O(\log(N+1))$개 대표 구간 중 답이 없는 구간은 최댓값 한 번으로 버릴 수 있다. 답이 있는 첫 구간에서는 리프로 향하는 경로만 더 내려가므로 질의도 $O(\log(N+1))$이다. 구간 최댓값 질의를 반복하며 별도로 이분 탐색할 필요가 없다.
전체 시간복잡도는 $O(N+Q\log(N+1))$, 공간복잡도는 $O(N)$이다.
구현 · 언어별 풀이
C++ 구현
세그먼트 트리의 탐색 함수에 노드 구간과 질의 구간, 기준값을 전달한다. 겹치지 않거나 최댓값이 작으면 $-1$을 반환하고 왼쪽 결과가 $-1$일 때만 오른쪽을 탐색한다. 값이 음수일 수 있으므로 저장 최댓값의 초기화를 $0$으로 대신하지 않는다.
C 구현
세그먼트 트리에 구간 최댓값을 저장한다. max < x인 노드를 건너뛰고 왼쪽부터 내려가 첫 위치를 찾는다.
Python 구현
max 트리를 리스트나 array('i')로 두고 왼쪽 자식부터 직접 탐색한다. 범위를 벗어나거나 최댓값이 $x$보다 작으면 실패한다. 전 원소가 음수여도 조회 기준을 $0$으로 초기화하지 않는다.
Java 구현
int[] max 트리에서 왼쪽 우선 하강을 한다. 조건에 맞는 왼쪽 결과가 있으면 오른쪽은 방문하지 않는다.
Rust 구현
부호 있는 max 배열과 usize 노드 인덱스를 사용한다. 왼쪽에서 답을 찾으면 바로 반환하고, 조건 불충족 시에만 오른쪽으로 간다. 부재 결과는 Option 또는 별도 sentinel로 구분한다.
JavaScript 구현
세그먼트 트리에는 구간 최댓값을 Int32Array로 저장한다. 입력 범위보다 작은 -2147483648로 비어 있는 칸을 초기화하면 음수 값에서도 최댓값을 보존한다.
탐색 함수는 공통 풀이처럼 왼쪽 자식부터 확인한다. 답은 지문의 $1$부터 시작하는 위치로 돌려주고, 찾지 못했을 때의 $-1$은 인덱스 보정 없이 반환한다.