쿼리가 주어진 순서와 가로줄을 지나는 순서는 서로 다르다. 쿼리 순서는 각 질문에 어떤 가로줄이 존재하는지를 결정하고, 높이 순서는 존재하는 가로줄을 어떤 순서로 지나는지를 결정한다. 전체 입력을 먼저 읽고 이 두 순서를 분리해서 처리한다.
번 쿼리의 개수를 라고 하고, 이 쿼리들에 등장 순서대로 의 번호를 붙인다. 가로줄을 추가할 때 그 전에 등장한 번 쿼리가 개였다면, 이 가로줄은 번호가 이상인 질문에만 존재한다. 따라서 각 가로줄에 연결하는 세로줄 , 높이 , 경계 를 저장한다. 이면 답을 출력할 쿼리가 없으므로 이 테스트 케이스의 처리를 끝낸다.
각 질문을 자신의 출발 세로줄에 놓인 공이라고 생각하자. 세로줄 마다 현재 그 줄에 있는 질문 번호의 집합 를 유지한다. 처음에는 로 주어진 질문의 번호를 에 넣는다.
모든 가로줄을 높이 의 오름차순으로 정렬하여 위에서부터 처리한다. 인 가로줄에 도달하면 와 에서 번호가 이상인 원소만 서로 교환한다. 번호가 보다 작은 질문에는 이 가로줄이 아직 추가되지 않았으므로 영향을 주지 않는다. 같은 높이의 가로줄은 세로줄을 공유하지 않으므로 어느 순서로 처리해도 된다.
이 교환을 빠르게 수행하기 위해 각 집합을 좌표 구간 의 동적 세그먼트 트리로 저장한다. 질문 번호가 들어 있는 리프와 그 조상만 필요한 만큼 만든다. 모든 세로줄의 트리는 같은 방식으로 구간을 나누므로, 같은 구간을 나타내는 두 부분 트리를 통째로 교환할 수 있다.
두 트리에서 구간 을 교환하는 연산은 다음과 같다. 현재 두 노드가 나타내는 구간을 라고 하자.
두 트리가 모두 비어 있으면 즉시 끝낼 수 있다. 일부만 교환해야 하는데 한쪽 노드가 없다면, 그쪽에 빈 노드를 만들어 두 자식을 관리한다. 노드의 참조를 교환할 때에는 부분 트리를 복사하지 않는다.
각 깊이에서 경계 를 내부에 포함하는 구간은 최대 하나뿐이다. 나머지 구간은 아예 교환하지 않거나 부분 트리 하나를 통째로 교환한다. 따라서 한 가로줄의 처리는 시간에 끝나며, 새로 만드는 노드도 그만큼이다.
모든 가로줄을 처리한 뒤 각 세로줄 의 트리를 순회한다. 그 트리에 질문 번호 의 리프가 있다면 로 기록한다. 이후 질문 번호 순서대로 답을 출력한다.
가로줄의 개수를 이라 하면 이다. 초기 트리 구성에는 , 가로줄 정렬에는 , 모든 교환에는 시간이 걸린다. 세로줄의 루트를 준비하고 마지막 트리 순회를 하는 비용을 포함한 전체 시간 복잡도는 이다. 초기 삽입과 각 교환에서 만드는 노드 수를 합하면 공간 복잡도도 이다.
증명
질문 번호 와 가로줄 하나를 고정하자. 이 가로줄을 추가하기 전에 등장한 질문이 개이면, 인 질문은 가로줄 추가 이전에, 인 질문은 그 이후에 주어졌다. 따라서 질문 의 사다리에 이 가로줄이 존재하는 조건은 정확히 이다.
Solution written by GPT6
높이순으로 가로줄을 처리하면서, 각 질문 번호는 해당 질문의 사다리에서 지금까지 처리한 높이까지 내려왔을 때의 세로줄 집합에 들어 있다는 불변식을 유지한다. 처음에는 각 질문을 자신의 출발 세로줄에 놓았으므로 성립한다.
인 가로줄을 처리한다고 하자. 이면 질문 에는 이 가로줄이 없으므로 위치가 변하지 않아야 한다. 이면 번 또는 번 세로줄에 있을 때만 반대편으로 이동해야 한다. 다른 세로줄에 있으면 변하지 않는다. 두 집합에서 번호가 이상인 부분만 교환하는 연산은 바로 이 이동을 수행한다. 세그먼트 트리의 재귀는 교환 구간 안의 리프만 정확히 교환하므로 그 결과를 그대로 구현한다. 따라서 불변식이 유지된다.
같은 높이의 가로줄들은 서로 다른 세로줄 쌍을 사용하므로 연산 순서가 결과에 영향을 주지 않는다. 모든 가로줄을 처리하면 각 질문은 그 질문에 존재하는 모든 가로줄을 위에서부터 지난 상태이다. 불변식에 의해 마지막에 속한 집합의 세로줄 번호가 실제 도착점이므로 출력한 답은 모두 정확하다.
