본문 바로가기

반응형

세그먼트트리

[BOJ 17353] 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 [문제] www.acmicpc.net/problem/17353 17353번: 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 욱제의 은밀한 취미 중 하나는 매일 밤하늘을 감상하는 것이다. 😓 욱제는 하늘의 별들이 다음과 같은 규칙들을 따르며 떨어지는 걸 관찰했다. 별이 떨어지는 위치는 N개의 점이다. 점은 순 www.acmicpc.net [난이도] - Platinum II (solved.ac 20.12.22 기준) [필요 개념] - Lazy Propagation with Segment Tree - Fenwick Tree 디스크립션은 간단하다. 두 종류의 쿼리가 들어오고, 한 쿼리는 구간 [L, R]에 순서대로 1, 2, ..., R-L+1을 더해준다. 나머지 한 쿼리는 X번째 원소의 값을 출력해준..
[BOJ 2336] 굉장한 학생 [문제] : https://www.acmicpc.net/problem/2336 2336번: 굉장한 학생 문제 N명의 학생이 참여하여 세 번의 시험을 치렀다. N명의 학생들은 세 번의 시험에 모두 응시하였다. 조교는 각각의 시험에서 같은 등수의 학생이 한 명도 없도록 성적을 매겼다. A라는 학생이 www.acmicpc.net [난이도] - Platinum 2 (2020.08.05 solved.ac 기준) [개념] - 세그먼트 트리 (Segment Tree) [풀이] 우선 https://jason9319.tistory.com/57 블로그의 설명을 참고하여 풀이를 하였다. 문제를 요약하자면, 각 학생이 세 번의 시험에 참여하였고, 학생 A보다 세 과목이 모두 더 높은 등수인 사람이 없다면 A를 '굉장하다'라고..