[백준][BOJ1321] 군인

Algorithm/Indexed Tree

by bedamino 2021. 9. 18. 19:27

1. 문제 : https://www.acmicpc.net/problem/1321

1321번: 군인

첫째 줄에 부대의 개수 N(1 ≤ N ≤ 500,000)이 주어지고, 이어서 각 부대의 군사 수를 나타내는 정수가 N개 주어진다. 각 부대의 군사 수는 1000보다 작거나 같은 자연수이다. 그 다음 줄에 명령의 개

www.acmicpc.net

2. 풀이 : Indexed Tree

3. 설명

각 부대의 군사 수 1, 4, 3, 5, 2를 구간합 트리로 표현하면 그림[1]과 같다.

그림[1]에서 6번 군인은 3번 부대에 속해 있으며, 6번 군인을 탐색하는 과정은 그림[2]와 같다.

2번 부대에서 3명의 감원이 일어나면 그림[3]과 같이 구간합 트리가 업데이트 된다.

그림[3]에서 6번 군인은 4번 부대에 속해 있으며, 6번 군인을 탐색하는 과정은 그림[4]와 같다.

4. 코드

저작자표시 비영리 변경금지

[백준][BOJ1572] 중앙값 (0)	2021.06.03

날마다 새로운 코딩