MathTrauma

문제 링크 : https://www.acmicpc.net/problem/11932 11932번: 트리와 K번째 수 첫째 줄에는 두 개의 양의 정수 N과 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 각 정점의 가중치를 나타내는 N개의 정수가 주어진다. i번째 정수는 i번 정점의 가중치이다. 이 가중치는 모두 www.acmicpc.net persistent segment tree + lca 로 해결했다. (더 나은 방법은 없을까?) lca 를 위한 dfs 를 거치면서 부모 노드가 각 자식노드를 생성하는 segment tree 이다. 최소공통조상(lca)는 아래 글에서 간략히 정리해 두었으니 참조. BOJ 3584 Nearest Common Ancestors BOJ 3584 Nearest..

문제 링크 : https://www.acmicpc.net/problem/13537 13537번: 수열과 쿼리 1 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다. www.acmicpc.net 수열이 모두 입력되고 나서 쿼리가 따로 주어지므로 소위 off-line query로 해결하라는 거 같은데... 익숙해지면 persistent segment tree 가 구현하기 오히려 편하게 느껴진다. persistent segment tree는 배열의 원소가 하나 추가될 때 마다 세그먼트 트리를 하나씩 만든다. 이 과정에서 메모리, 시간이 문제가 ..