수열과 쿼리
-
[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를 받게 된다. 지금보니 쿼리가 구간 쿼리가 아..