Segment Tree
-
[백준] 6549번 히스토그램에서 가장 큰 직사각형문제 풀이 2020. 8. 10. 21:25
6549 히스토그램에서 가장 큰 직사각형 문제히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오. 입력입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 ..
-
[백준] 13537번 수열과 쿼리1문제 풀이 2020. 7. 13. 18:39
13537 수열과 쿼리1 문제길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다. 입력첫째 줄에 수열의 크기 N (1 ≤ N ≤ 100,000)이 주어진다.둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)셋째 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다.넷째 줄부터 M개의 줄에는 쿼리 i, j, k가 한 줄에 하나씩 주어진다. (1 ≤ i ≤ j ≤ N, 1 ≤ k ≤ 109) 출력각각의 쿼리마다 정답을 한 줄에 하나씩 출력한다. 풀이)수열의 길이도 10만까지 되며, 쿼리의 수도 10만까지 주..
-
[백준] 1395번 스위치문제 풀이 2020. 4. 11. 00:06
1395 스위치 문제준규네 집에는 총 N개의 스위치가 있고 이를 편하게 1번부터 N번까지 차례대로 번호를 매겼다. 그리고 준규의 취미는 이 스위치들을 켜고 끄는 것이다.준규가 하는 스위치를 갖고 노는 일은 크게 두 가지이다. 하나는 A번부터 B번 사이의 스위치 상태를 반전시키는 것이고 다른 하나는 C번부터 D번 사이의 스위치 중 켜져 있는 상태의 스위치의 개수를 세는 것이다.하지만 준규가 싫증을 느껴 우리가 이 귀찮은 일을 떠맡게 되었고 프로그래밍을 통해 일을 처리하도록 결정하였다. 입력첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti..
-
Segment Tree알고리즘 2020. 3. 17. 17:20
Segment Tree 세그먼트 트리개념 : 배열의 특정 구간의 합, 혹은 특정 구간에서 최대값·최솟값 등을 효율적으로 구하기 위한 자료구조기본 구조 : 완전 이진 트리 구조 가장 최상단인 루트 노드 - 전체 구간의 정보 가장 최하단의 리프 노드 - 배열의 그 수 자체 즉 배열의 각 요소 배열의 크기가 N = 10개 일때의 세그먼트 트리를 그리면, 세그먼트 트리는 1차원 배열로 구현한다. 크기 : 입력 배열의 크기가 N일때, 리프 노드의 개수가 N이 된다. 따라서 세그먼트 트리의 높이는 [logN]이 되고, 세그먼트 트리 배열의 크기는 2^(H+1) 이 된다. 이를 코드로 나타내면12int h = (int)ceil(log2(n));int tree_size = (1