반응형
https://www.acmicpc.net/problem/14463
14463번: 소가 길을 건너간 이유 9
첫 줄에 N (1 ≤ N ≤ 50,000)이 주어진다. 다음 2N줄에는 한 줄에 하나씩 길 위의 점을 지나간 소의 번호가 주어진다.
www.acmicpc.net
[ 문제풀이 ]
이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.
https://rudalsd.tistory.com/364
[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)
1. 비재귀 세그먼트 트리 (Segment Tree) 재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다. 2. 비재귀 세그먼트
rudalsd.tistory.com
1. visited 배열을 선언하고, 소가 나오면 해당 위치를 visited 배열에 저장하고, 해당 위치의 Segment Tree 노드에 1을 더해줍니다.
2. 만약 입력받은 수가 이미 방문을 했다면 visited[ n ] + 1 ~ i - 1 까지의 구간합을 ans에 더해주고, visited[ n ]의 Segment Tree 노드에 -1을 해줍니다.
3. ans를 출력합니다.
[ 소스코드 ]
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 | #include<iostream> using namespace std; int N; int visited[50001]; int segTree[200000]; void updateTree(int idx, int diff) { while (idx != 0) { segTree[idx] += diff; 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); int ans = 0; for (int i = 1; i <= 2 * N; i++) { int a; scanf("%d", &a); if (visited[a] == 0) { visited[a] = i; updateTree(2 * N + i - 1, 1); } else { ans += getTree(2 * N + visited[a], 2 * N + i - 2); updateTree(2 * N + visited[a] - 1, -1); } } printf("%d", ans); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 20437번 - 문자열 게임 2 (C++) (0) | 2023.06.13 |
|---|---|
| [ 백준 ] 12919번 - A와 B 2 (C++) (0) | 2023.06.12 |
| [ 백준 ] 5817번 - 고통받는 난쟁이들 (C++) (0) | 2023.06.10 |
| [ 백준 ] 14449번 - Balanced Photo (C++) (0) | 2023.06.09 |
| [ 백준 ] 11962번 - Counting Haybales (C++) (0) | 2023.06.08 |