[3770] 대한민국

https://www.acmicpc.net/problem/3770

 

세그먼트 트리문제다. [7578] 공장 문제와 같은 풀이로 접근가능하다.

 

풀이

[7578] 공장 문제와 달리 유의할 점은 입력되는 간선의 정렬이 필요하다는 점이다.

 

출발지 기준 오름차순, 출발지가 같다면 도착지기준 오름차순으로 고속도로 정보를 정렬한 뒤, 매 순간 도착도시 다음번호 ~ 마지막 도착도시 구간의 건설된 고속도로의 개수 총합을 출력하면 된다.

 

입력 예제를 기준으로 시나리오를 그려보면 다음과 같다.

 

좌측의 N개의 도시, 우측의 M개의 도시와 정렬된 간선 그리고 구간 합 세그먼트 트리를 생성한다.

 

1번 도시와 4번 도시를 연결, 4번은 가장 마지막 도시이므로 구간합 조회 시 범위를 넘어가게 되어 0을 반환하게 된다.

다음 탐색을 위해 4번 노드에 1 추가.

 

2번 도시와 3번 도시 연결, 이때 3번 도시 이후의 구간 즉 4~4번 구간의 고속도로의 개수 1을 정답에 추가한다.

이후 3번 노드에 1 추가.

 

3번 도시와 1번 도시 연결, 2번 도시부터 4번 도시 구간의 고속도로의 수를 조회한다. 고속도로의 개수 2가 반환된다.

이후 1번 노드에 1 추가.

 

마지막으로 3번 도시와 2번 도시 연결, 3번 도시와 4번 도시 구간합을 조회. 정답에 해당 구간값 2를 추가한다.

2번 노드에 1 추가.

 

정답 코드