题目描述

A pasture in the wild west can be represented as a rectangular grid embedded in the upper-right quadrant of a standard coordinate system. A herd of $n$ buffalos is scattered throughout the grid, each occupying a unit square. Buffalos are numbered $1$ through $n$; buffalo $j$ is located in the unit square whose upper-right corner is the point with integer coordinates $(x_j,y_j)$. The coordinate axes represent two rivers meeting at the origin, restricting buffalo movement downwards and leftwards.

A total of $m$ settlers arrive, one by one, and each claims a piece of land using the following procedure:

1. The settler picks a point with integer coordinates and installs a single fence post at that point.The point he picks is guaranteed to be free of any previously installed fence posts or fences.Moreover, no two fence posts will have the same $x$-coordinate and no two fence posts will have the same $y$-coordinates.
2. Starting from the fence post, the settler builds horizontal and vertical fence segments leftwards and downwards, respectively. Each segment is built to be as long as possible — i. e. until it reaches the river or another fence.
3. The settler claims all the land in the connected area bounded with fences and rivers whose upper-right corner is his fence post. Of course, he claims all the buffalos inside as well. Note that settlers arriving later may claim pieces of land already claimed by earlier settlers.

For each settler, find the total number of buffalos he claimed when he arrived.

输入格式

The first line contains an integer $n(1 \le n \le 300 000)$ — the number of buffalos. The $j-th$ of the following $n$ lines contains two integers $x_j$ and $y_j(1 \le x_j,y_j \le 10^9)$ — the location of the $j-th$ buffalo.No two buffalos will share the same location. The following line contains an integer $m(1 \le m \le 300 000)$ — the number of settlers. The $j-th$ of the following $m$ lines contains two integers $x^{'}_{j}$ and $y^{'}_{j}(1 \le x^{'}_{j},y^{'}_{j} \le 10^9)$ — the coordinates of the fence postinstalled by the $j-th$ settler. All $x^{'}_{j}$ are different and all $y^{'}_{j}$ are different.

输出格式

Output $m$ lines. The $j-th$ line should contain the number of buffalos claimed by the $j-th$ settler upon arrival.

题目大意

【题目描述】

（西进运动时期）美国西部的一块牧场可以被表示为坐标系第一象限中的一块矩形网格。有 $n$ 头水牛在其中分布着，每一头都占据着一个单位正方形。水牛们从 $1$ 到 $n$ 编号；$j$ 号水牛位于右上角坐标为 $(x_j, y_j)$ 的单位正方形中。坐标轴表示了两条交汇于原点处的河流，阻止水牛向左下方移动。

一共有 $m$ 个殖民者接连到达，每个人都要宣称一块土地的所有权，其过程遵循以下规则：

1. 殖民者选定一个整数坐标点，并在此处安装一个栅栏柱。他选定的点必须没有被此前安装的栅栏或栅栏柱占据。并且，不存在两个栅栏柱会拥有相同的 $x$ 坐标，也不存在两个栅栏柱会拥有相同的 $y$ 坐标。
2. 从栅栏柱开始，殖民者分别朝着左侧或下侧修建水平或竖直的栅栏片段。每段栅栏都修建得尽可能长：即直到碰到了河流或另一段栅栏才停下。
3. 殖民者宣称以他的栅栏柱为右上角的，被栅栏和河流包围住的连通区域的所有权。当然，他也宣称了其中的所有水牛的所有权。注意后到来的殖民者也有可能宣称了已被先到来的殖民者宣称过的土地。

对于每个殖民者，请求出当他刚到来时，被他宣称了所有权的水牛的数量。

【输入格式】

第一行一个正整数 $n$，表示水牛的个数。

接下来 $n$ 行，第 $j$ 行两个正整数 $x_j, y_j$，表示第 $j$ 头水牛的位置，不存在两头水牛的位置重合。

接下来一行一个正整数 $m$，表示殖民者的个数。

接下来 $m$ 行，第 $j$ 行两个正整数 $x'_j, y'_j$，表示第 $j$ 个殖民者安装的栅栏柱的位置，所有 $x'_j$ 互不相同，所有 $y'_j$ 互不相同。

【输出格式】

输出 $m$ 行，第 $j$ 行一个整数，表示第 $j$ 个殖民者刚到来时，被他宣称了所有权的水牛的数量。

【数据范围】

对于全部数据，$1 \le n, m \le 3 \times {10}^5$，$1 \le x_j, y_j, x'_j, y'_j \le {10}^9$，所有有序数对 $(x_j, y_j)$ 互不相同，所有 $x'_j$ 互不相同，所有 $y'_j$ 互不相同。

翻译来源：IOI 2021 集训队第一部分作业，PinkRabbit。

7
1 1
4 2
6 2
5 3
2 5
4 7
7 5
4
4 4
8 2
9 6
6 5

2
1
3
2