반응형
https://www.acmicpc.net/problem/12899
12899번: 데이터 구조
첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000) 둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다. T가 1이라면 S에 추가할 X가 주어지는 것입니
www.acmicpc.net
[ 문제풀이 ]
이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.
https://rudalsd.tistory.com/51
[ 자료구조 ] 세그먼트 트리 (Segment Tree)
1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1
rudalsd.tistory.com
1. 쿼리 업데이트를 통해 해당 자연수 노드에 1을 더해주고, 구간 합을 세그먼트 트리를 이용하여 구현해 줍니다.
2. 왼쪽 노드의 값이 원하는 인덱스의 값보다 크다면 왼쪽 노드로 들어가고, 그렇지 않다면 인덱스의 값에 왼쪽 노드의 값을 뺀 값을 이용하여 오른쪽 노드로 들어가 줍니다.
3. 원하는 인덱스의 노드 번호를 출력해 줍니다.
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | #include<iostream> using namespace std; int N; int segTree[4200000]; void updateTree(int node, int s, int e, int idx) { if (idx < s || e < idx) return; segTree[node]++; if (s != e) { int m = (s + e) / 2; updateTree(node * 2, s, m, idx); updateTree(node * 2 + 1, m + 1, e, idx); } } void getTree(int node, int s, int e, int idx) { if (s == e) { printf("%d\n", s); segTree[node]--; return; } int m = (s + e) / 2; if (segTree[node * 2] >= idx) { getTree(node * 2, s, m, idx); segTree[node]--; } else { getTree(node * 2 + 1, m + 1, e, idx - segTree[node*2]); segTree[node]--; } } int main() { scanf("%d", &N); for (int i = 0; i < N; i++) { int cmd, X; scanf("%d %d", &cmd, &X); if (cmd == 1) { updateTree(1, 1, 2000000, X); } else { getTree(1, 1, 2000000, X); } } } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 7511번 - 소셜 네트워킹 어플리케이션 (C++) (0) | 2023.05.30 |
|---|---|
| [ 백준 ] 17352번 - 여러분의 다리가 되어 드리겠습니다! (C++) (0) | 2023.05.29 |
| [ 백준 ] 18116번 - 로봇 조립 (C++) (0) | 2023.05.27 |
| [ 백준 ] 11376번 - 열혈강호 2 (C++) (0) | 2023.05.26 |
| [ 백준 ] 11375번 - 열혈강호 (C++) (0) | 2023.05.25 |