Segment Tree
-
[백준] 14287 - 내리 갈굼 3Algorithm 문제 2019. 12. 19. 16:01
https://www.acmicpc.net/problem/14287 14287번: 내리 갈굼 3 영선회사에는 치명적인 악습이 있는데, 바로 상사가 직속 부하를 갈구면 그 부하가 부하의 직속 부하를 연쇄적으로 갈구는 내리 갈굼이 있다. 즉, 상사가 한 직속 부하를 갈구면 그 부하의 모든 부하들이 갈굼을 당한다. 이러한 내리 갈굼은 회사에 가장 큰 불만 사항이 되었고, 사장 영선이는 이 불만을 해소해주기 위하여, 단 하루만 야자타임식으로 하여, 반대로 부하가 상사를 갈구면, 그 위로 쭉 사장까지 모두 갈굼을 당한다. 갈굼의 대한 정보는 실시간으로 주어진 www.acmicpc.net 내리 갈굼 2 문제에서 거꾸로 부하가 상사를 갈구는 문제. 상사가 받은 갈굼 정도는 부하들이 받은 내리갈굼의 합과 같다. 전위순..
-
[백준] 2820 - 자동차 공장Algorithm 문제 2019. 12. 18. 17:45
https://www.acmicpc.net/problem/2820 2820번: 자동차 공장 문제 상근이는 자동차를 매우 좋아한다. 자동차 공장에 취직한 상근이는 계속된 승진 끝에 드디어 사장이 되었다. 공장에는 총 N명의 직원이 있다. 상근이를 제외한 모든 직원은 한 명의 상사가 있다. (상근이는 모든 사람의 상사이다) 상근이의 번호는 1번이고, 나머지 직원의 번호는 2부터 N이다. 모든 직원은 자신의 모든 부하 직원(직속 부하와 부하의 부하등등을 모두 포함)의 월급을 인상하거나 삭감할 수 있다. 상근이는 권력 남용을 막기 위해 직원의 월급을 www.acmicpc.net 구간합을 구하는 문제는 아니지만 트리에서 자식들의 갱신이 이루어지는 문제이므로 segment tree와 lazy propagation을..
-
[백준] 14268 - 내리 갈굼 2Algorithm 문제 2019. 12. 9. 20:13
https://www.acmicpc.net/problem/14268 14268번: 내리 갈굼 2 영선회사에는 치명적인 악습이 있는데, 바로 상사가 직속 부하를 갈구면 그 부하가 부하의 직속 부하를 연쇄적으로 갈구는 내리 갈굼이 있다. 즉, 상사가 한 직속 부하를 갈구면 그 부하의 모든 부하들이 갈굼을 당한다. 갈굼에 대해 정도에 대한 수치가 주어지는데, 이 수치 또한 부하들에게 똑같이 갈궈진다. 이번에는 내리 갈굼이 실시간으로 일어날 것이다. 입력으로 아래와 같은 쿼리가 주어질 것이다. 1 i w : i번째 직원이 직속 상사로부터 w만큼 갈굼을 당한 www.acmicpc.net 앞선 내리 갈굼 문제에서 갱신 중간에 쿼리가 주어지는 문제이다. 내리 갈굼 문제의 알고리즘에서 dfs를 이용하여 해당 사원의 상..
-
[백준] 2357 - 최솟값과 최댓값Algorithm 문제 2019. 11. 30. 16:46
https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자. 여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을 www.acmicpc.net Segment Tree를 이용하여 시간을 단축할 수 있는 문제 아래의 페이지에 설명이 잘 정리되어 있다. https://www.ac..