Barbera

필요한 배경지식 세그먼트 트리 Inversion Counting Inversion은 다음과 같이 정의됩니다. 길이가 N인 배열 A[1], A[2], ..., A[N]이 주어질때, $ i A[j] $를 만족할때 $A[i]$와 $A[j]$는 Inversion관계이다. Inversion Counting은 위에서 설명한 Inversion관계의 총 개수를 찾는 문제 입니다. 배열이 정렬이 되어 있을때는 Inversion Counting이 0이 되지만 역순으로 정렬되어 있다면 최대가 됩니다. Inversion쌍을 구하기 위한 방법으로 완전탐색을 생각해보면 \( O(N^{2}) \)의 시간복잡도로 모든 쌍을 비교해 볼 수 있지만 대부분의 문제에서 시간안에 해결할 수 없습니다. 이 문제..

https://www.acmicpc.net/problem/5916 5916번: 농장 관리 첫째 줄에 농장의 수 N과 쿼리의 수 M(1 ≤ N, M ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 도로가 연결하는 농장의 번호가 주어진다. 다음 M개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. www.acmicpc.net HLD 풀이가 정해이지만 LCA + 세그트리로 해결할 수 있습니다. 필요한 배경지식 최소 공통 조상(LCA) 세그먼트 트리 오일러 투어 테크닉 문제 해결 방법 우선 N개의 노드와 N-1개의 간선이 존재하므로 농장은 트리 형태의 자료구조를 가진다는것을 확인할 수 있습니다. 이 문제에서 조심해야 할 부분으로는 P와 Q쿼리 모두 노드가 아닌 간선의 값을 처리해야 하기 때문에 모든 간..