https://www.acmicpc.net/problem/7578
7578호:공장
일부 공장에서는 2N대의 기계가 N대씩 2열로 배열되어 있습니다. 이 두 열을 각각 A열과 B열이라고 합니다. A열에 있는 N개의 기계 각각은 B열에 있는 N개의 기계와 쌍을 이룹니다.
www.acmicpc.net
세그먼트 트리 문제입니다.
설명
A 열의 왼쪽부터 연결하여 계산해야 합니다. A컬럼별로 B컬럼에 있는 머신 번호를 파악한 후 해당 위치에서 N-1에 연결된 머신의 번호를 저장합니다. 세그먼트 트리와 사전을 사용하여 액세스했습니다.
이것은 다음과 같은 예를 사용하여 설명됩니다.
열 A의 기계 번호 0은 열 B의 번호 2에 있습니다. 연결된 기계 수를 0에서 4까지 쿼리하십시오.
+0 세그먼트에 연결된 기계가 없기 때문입니다.
다음으로 열 A의 기계 번호 1은 열 B의 번호 0에 있습니다. 섹션 0-4에서 연결된 기계의 수를 쿼리하십시오.
하나(2번)가 있기 때문에 +1입니다.
A열 2번은 B열 3번입니다. 3-4구간 검색.
없기 때문에 +0.
A컬럼 4번은 B컬럼 1번에서 섹션 1~4를 검색합니다.
2개(숫자 2와 3)가 있으므로 +2입니다.
마지막으로 A열의 4번은 B열의 4번입니다.
이것이 마지막 색인이므로 그 뒤에 연결된 기계가 없습니다. 즉, 정답은 3번입니다.
올바른 응답 코드
