반응형
https://www.acmicpc.net/problem/1615
1615번: 교차개수세기
첫 줄에 N과 간선의 개수 M이 주어진다. 그 다음 줄부터 M+1번째 줄까지 두 개의 수(i, j)가 주어지는데 이는 왼쪽 그룹의 i번 정점과 오른쪽 그룹의 j번 정점을 연결하는 간선이 있다는 의미이다.
www.acmicpc.net
[ 문제풀이 ]
이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.
https://rudalsd.tistory.com/51
[ 자료구조 ] 세그먼트 트리 (Segment Tree)
1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1
rudalsd.tistory.com
1. 입력받은 수를 첫번 째 수를 기준으로 오름차순으로 정렬합니다.
2. for문을 통해 반복하면서 두번 째 수를 인덱스로 segment tree를 업데이트 합니다.
3. 이후 두번 째 수부터 N까지 구간 합을 ans에 더해줍니다.
4. 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 | #include<iostream> #include<algorithm> #define ll long long using namespace std; int N, M; pair<int, int> arr[2000000]; ll segTree[5000]; void updateTree(int node, int s, int e, int idx) { if (s > idx || e < idx) return; segTree[node] += 1; if (s != e) { int m = (s + e) / 2; updateTree(node * 2, s, m, idx); updateTree(node * 2 + 1, m + 1, e, idx); } } ll sumTree(int node, int s, int e, int sidx, int eidx) { if (s > eidx || e < sidx) return 0; if (sidx <= s && e <= eidx) return segTree[node]; int m = (s + e) / 2; ll left = sumTree(node * 2, s, m, sidx, eidx); ll right = sumTree(node * 2 + 1, m + 1, e, sidx, eidx); return left + right; } int main() { scanf("%d %d", &N, &M); for (int i = 0; i < M; i++) { scanf("%d %d", &arr[i].first, &arr[i].second); } sort(arr, arr + M); ll ans = 0; for (int i = 0; i < M; i++) { int cur = arr[i].second; updateTree(1, 1, N, cur); ans += sumTree(1, 1, N, cur + 1, N); } printf("%lld", ans); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 9463번 - 순열 그래프 (C++) (0) | 2023.01.23 |
|---|---|
| [ 백준 ] 10090번 - Counting Inversions (C++) (0) | 2023.01.22 |
| [ 백준 ] 1777번 - 순열복원 (C++) (0) | 2023.01.20 |
| [ 백준 ] 1849번 - 순열 (C++) (0) | 2023.01.19 |
| [ 백준 ] 16975번 - 수열과 쿼리 21 (C++) (0) | 2023.01.18 |