산책길
시간 제한1초메모리 제한128 MB
최대 30만 개 점과 10만 개의 직사각형 질의가 주어질 때 각 직사각형 테두리 위에 놓인 점의 개수를 구하는 문제입니다.
문제
정부는 오크나무 숲을 지나는 산책로를 만들려고 한다. 숲은 평면으로 나타낼 수 있고, 나무 N그루는 서로 다른 격자점에 서 있다.
산책로는 좌표축에 평행한 직사각형으로 표현된다. 직사각형의 변 위에 있는 나무는 베어야 하지만, 직사각형의 내부에 있는 나무는 베지 않아도 된다.
산림청에는 총 P개의 산책로 계획이 접수되었다. 각 계획에 대해, 그 산책로를 만들기 위해 베어야 하는 나무의 수를 구하라. 베어야 하는 나무는 직사각형의 변 위에 있는 나무뿐이다.
입력
첫째 줄에 나무의 수 N이 주어진다. (1 <= N <= 300,000)
다음 N개 줄에는 나무 한 그루의 좌표 X와 Y가 한 줄에 하나씩 주어진다. 같은 점에 두 그루 이상의 나무가 있는 경우는 없다. (1 <= X, Y <= 10^9)
다음 줄에는 접수된 산책로 계획의 수 P가 주어진다. (1 <= P <= 100,000)
다음 P개 줄에는 X1, Y1, X2, Y2가 주어진다. (1 <= X1 < X2 <= 10^9, 1 <= Y1 < Y2 <= 10^9) (X1, Y1)은 직사각형의 왼쪽 아래 좌표, (X2, Y2)는 오른쪽 위 좌표를 나타낸다.
출력
P개의 줄에 걸쳐 각 산책로를 건설하기 위해 베어야 하는 나무의 수를 입력으로 주어진 계획 순서대로 출력한다.
힌트
