2017/06/04 썸네일형 리스트형 BOJ)14577 일기예보 문제:icpc.me/14577 4가지 종류의 질의가 들어오는 문제이다. 지역 수 가 N 질의의 수가 M일 때 N,M이 10만까지 들어오므로 적어도 질의 하나당 log 시간에 해결해줘야 한다. 결국 3,4번 질의를 로그시간에 답해줘야 하는데 구간에 대한 질의이므로 우선 세그먼트 트리를 생각해낼 수 있다. 하지만 좌표 자체에 업데이트를 할 경우 좌표의 범위부터가 감당이 안된다. 그렇기 때문에 우리는 한 지역에 쌓일 수 있는 눈의 양에 업데이트를 해야한다. 나올 수 있는 눈의 양은 3번 쿼리의 경우 2개 1,2번 쿼리의 경우 1개 일 뿐이니 최대 2*M개 뿐이기 때문이다. 말을 어렵게 표현했는데 우선 쿼리를 오프라인으로 처리할거다. 모든 쿼리를 받은 뒤에 해당 질의 때 마다 나올 수 있는 모든 눈의 양을 저장.. 더보기 이전 1 다음