BOJ 11932 트리와 K번째 수
문제 링크 : 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..
DS\Algo
2022. 8. 26. 13:36
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- bash
- stack
- Vim
- fenwick tree
- BOJ
- number theory
- map
- shell
- JavaScript
- 다익스트라
- Aho-Corasick
- 정수론
- Dijkstra
- max flow
- script
- nearest common ancestor
- 백준
- persistent segment tree
- Reference
- bash script
- 세그먼트 트리
- math font
- javascript array
- segment tree
- Shell Programming
- C++ big number
- python3
- RUBY
- dynamic programming
- lazy propagation
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |
글 보관함