백준 14897번: 서로 다른 수와 쿼리 (Segment Tree) 문제링크: 14897번: 서로 다른 수와 쿼리 1 (acmicpc.net) 14897번: 서로 다른 수와 쿼리 1 첫째 줄에 배열의 크기 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 배열에 포함된 수가 1번째 수부터 주어진다. 수는 공백으로 구분되어져 있다. 배열에 포함된 수는 1,000,000,000보다 작거나 같 www.acmicpc.net 이 문제는 배열 A의 길이 N이 N 백준 2023.03.02
백준 13537번: 수열과 쿼리 1 (Merge sort tree) 문제링크:13537번: 수열과 쿼리 1 (acmicpc.net) 13537번: 수열과 쿼리 1 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다. www.acmicpc.net 이 문제는 길이가 N인 수열이 있을 때, 쿼리의 입력이 (i, j, k) 이렇게 주어지면 i번째부터 j번째 까지의 수열의 원소 중 k 보다 큰 값들의 개수를 출력하는 문제이다. 여기서 N의 최대값은 100,000, 쿼리의 개수의 최대값도 100,000 이기 때문에 불러오는 쿼리의 시간 복잡도를 O(logN) 선에서 처리해야 한다. 나는 전에 몇번 다루었던 merge .. 백준 2023.01.25