반응형
https://www.acmicpc.net/problem/3006
3006번: 터보소트
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이며, 배열의 크기이다. 둘째 줄부터 N개의 줄에는 1보다 크거나 같고, N보다 작거나 같은 수가 중복 없이 주어진다
www.acmicpc.net
[ 문제풀이 ]
이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.
https://rudalsd.tistory.com/364
[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)
1. 비재귀 세그먼트 트리 (Segment Tree) 재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다. 2. 비재귀 세그먼트
rudalsd.tistory.com
1. segmentTree의 리프노드를 모두 1로 채우고 나머지 노드들을 구간합으로 채워줍니다.
2. 배열을 입력 받고, 각 수의 위치를 arr 배열에 저장합니다.
3. 1부터 N까지 번갈아가며 홀수번째 단계에서는 0 ~ arr[ i ] - 1까지의 구간합을 출력하고, 짝수번째 단계에서는 arr[ i ] + 1 ~ 2N - 1까지의 구간합을 출력합니다.
[ 소스코드 ]
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 56 57 58 59 60 61 62 63 64 65 66 67 | #include<iostream> using namespace std; int N; int arr[100001]; int segTree[200000]; void updateTree(int idx, int k) { while (idx != 0) { segTree[idx] += k; idx >>= 1; } } int getTree(int l, int r) { int ret = 0; while (l <= r) { if (l & 1) { ret += segTree[l]; l++; } if (~r & 1) { ret += segTree[r]; r--; } l >>= 1; r >>= 1; } return ret; } int main() { scanf("%d", &N); for (int i = 0; i < N; i++) { int n; scanf("%d", &n); updateTree(N + i, 1); arr[n] = i; } int L = 1; int R = N; int cnt = 1; while (L <= R) { if (cnt & 1) { printf("%d\n", getTree(N, N + arr[L]) - 1); updateTree(N + arr[L], -1); L++; } else { printf("%d\n", getTree(N + arr[R], 2 * N - 1) - 1); updateTree(N + arr[R], -1); R--; } cnt++; } } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 2934번 - LRH 식물 (C++) (0) | 2023.05.23 |
|---|---|
| [ 백준 ] 14245번 - XOR (C++) (0) | 2023.05.22 |
| [ 백준 ] 1280번 - 나무 심기 (C++) (0) | 2023.05.20 |
| [ 백준 ] 2517번 - 달리기 (C++) (0) | 2023.05.19 |
| [ 백준 ] 17612번 - 쇼핑몰 (C++) (0) | 2023.05.18 |