문제
길이가 N인 수열 A가 주어진다. 다음 두 종류의 쿼리를 처리하는 프로그램을 작성하시오.
- 쿼리 1:
1 i v— A[i]를 v로 바꾼다. - 쿼리 2:
2— 수열에서 값이 가장 작은 원소의 인덱스를 출력한다. 값이 같은 원소가 여러 개라면 인덱스가 가장 작은 것을 출력한다.
입력
첫째 줄에 수열의 크기 N이 주어진다. 둘째 줄에 수열 A의 원소 N개가 공백으로 구분되어 주어진다. 셋째 줄에 쿼리의 수 M이 주어진다. 넷째 줄부터 M개의 줄에 쿼리가 주어진다.
- 1 ≤ N ≤ 100,000
- 1 ≤ M ≤ 100,000
- 1 ≤ A[i] ≤ 10^9
출력
쿼리 2에 대해 조건을 만족하는 인덱스를 한 줄에 하나씩 출력한다.
예제
입력:
5
4 3 2 1 5
3
2
1 3 10
2출력:
4
1풀이
핵심 아이디어: 세그먼트 트리의 각 노드에 값이 아닌 인덱스를 저장한다. 두 인덱스를 비교할 때 해당 인덱스가 가리키는 원소의 값을 비교하고, 값이 같으면 인덱스가 작은 쪽을 선택한다.
- 초기화: 세그먼트 트리를 구성한다. 리프 노드는 해당 위치의 인덱스 자체를 저장하고, 내부 노드는 자식 중 더 작은 값을 가진 인덱스를 저장한다.
- 업데이트 (쿼리 1): 배열의 특정 위치 값을 변경한다. 세그먼트 트리에서 해당 인덱스 위치를 업데이트하면 경로상의 모든 노드가 갱신된다.
- 최솟값 인덱스 조회 (쿼리 2):
tree[1]이 전체 범위의 최솟값 인덱스를 가리키므로 즉시 O(1)에 반환한다. - 비교 함수
getIdx:arr[left] == arr[right]이면 더 작은 인덱스를 반환하고, 그렇지 않으면 더 작은 값을 가진 인덱스를 반환한다.
각 쿼리는 세그먼트 트리 높이에 비례하여 O(log N)에 처리된다.
코드
package day349;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day325BOJ14427수열과쿼리15 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++)
arr[i] = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(br.readLine());
SegmentTree stree = new SegmentTree(arr, N + 1);
stree.init(1, N, 1);
StringBuilder sb = new StringBuilder();
while (M-- > 0) {
st = new StringTokenizer(br.readLine());
if (Integer.parseInt(st.nextToken()) == 1) {
// change a to b
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
stree.arr[a] = b;
stree.update(1, N, 1, a);
} else {
sb.append(stree.tree[1]).append("\n");
}
}
System.out.println(sb.toString());
}
}
class SegmentTree {
int[] arr;
int[] tree;
SegmentTree(int[] arr, int arr_size) {
this.arr = arr;
this.tree = new int[arr_size * 4];
}
int init(int start, int end, int node) {
if (start == end)
return tree[node] = start;
int mid = (start + end) / 2;
return tree[node] = getIdx(init(start, mid, node * 2), init(mid + 1, end, node * 2 + 1));
}
int getIdx(int left, int right) {
return arr[left] == arr[right] ? Math.min(left, right) : arr[left] < arr[right] ? left : right;
}
int update(int left, int right, int node, int idx) {
if (idx < left || right < idx)
return tree[node];
if (left == right)
return tree[node] = idx;
int mid = (left + right) / 2;
return tree[node] = getIdx(update(left, mid, node * 2, idx), update(mid + 1, right, node * 2 + 1, idx));
}
}복잡도
- 시간: O((N + M) log N) — 초기화 O(N log N), 각 쿼리 O(log N)
- 공간: O(N) — 세그먼트 트리 크기 4N