segment tree
-
[BOJ] 14428,14438 수열과 쿼리 16,17PS/BOJ 2020. 8. 23. 19:21
https://www.acmicpc.net/problem/14428 14428번: 수열과 쿼리 16 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값의 인덱스를 출력한다. 그러 www.acmicpc.net https://www.acmicpc.net/problem/14438 14438번: 수열과 쿼리 17 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에..
-
[BOJ] 14427 수열과 쿼리 15PS/BOJ 2020. 8. 23. 18:22
https://www.acmicpc.net/problem/14427 14427번: 수열과 쿼리 15 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 가장 작은 값의 인덱스를 �� www.acmicpc.net 알고리즘: Segment tree 시간복잡도: $O((M+N)logN)$ 접근: 1. 많은 수의 쿼리 ($1\le M\le 10^5$) 일단 쿼리 수가 너무 많다는 점에서 나이브한 방법으로는 안된다는 걸 알 수 있다. 매 쿼리마다 최솟값을 구하다 보면 시간복잡도가 $O(MN)$이 나와 TLE를 받게 된다. 지금보니 쿼리가 구간 쿼리가 아..