반응형
https://www.acmicpc.net/problem/2517
2517번: 달리기
첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는
www.acmicpc.net
[ 문제풀이 ]
이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.
https://rudalsd.tistory.com/364
[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)
1. 비재귀 세그먼트 트리 (Segment Tree) 재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다. 2. 비재귀 세그먼트
rudalsd.tistory.com
1. arr 배열에 실력을 저장하고, vector<int> list에 실력을 저장하고, 오른차순으로 정렬합니다.
2. for문으로 arr배열을 돌면서 lower_bound를 활용하여 해당 실력이 몇번 째 순서인지 확인하고, segmentTree를 업데이트 해줍니다.
3. query를 이용하여 해당 실력부터 가장 실력이 높은 값까지 합을 출력합니다.
[ 소스코드 ]
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 | #include<iostream> #include<vector> #include<algorithm> using namespace std; int N; vector<int> list; int arr[500001]; int segTree[1000000]; void updateTree(int idx) { while (idx != 0) { segTree[idx] += 1; idx >>= 1; } } int query(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 a; scanf("%d", &a); list.push_back(a); arr[i] = a; } sort(list.begin(), list.end()); for (int i = 0; i < N; i++) { int cur = lower_bound(list.begin(), list.end(), arr[i]) - list.begin(); updateTree(cur + N); printf("%d\n", query(N + cur, 2 * N - 1)); } } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 3006번 - 터보소트 (C++) (0) | 2023.05.21 |
|---|---|
| [ 백준 ] 1280번 - 나무 심기 (C++) (0) | 2023.05.20 |
| [ 백준 ] 17612번 - 쇼핑몰 (C++) (0) | 2023.05.18 |
| [ 백준 ] 14588번 - Line Friends (Small) (C++) (0) | 2023.05.17 |
| [ 백준 ] 9879번 - Cross Country Skiing (C++) (0) | 2023.05.16 |