Logo Universal Online Judge

UOJ

时间限制:2 s 空间限制:1024 MB
Statistics

不知道咋改空间限制,所以最后一个子任务开的是 1024M

题目大意

平面上有 $n$ 个位置不同的点,每个点有一个颜色,有 $q$ 次询问,每次询问输出矩形内的点的颜色数。

输入格式

第一行两个整数 $n,q$,表示点数和询问数。

接下来 $n$ 行,每行两个整数 $p_i,c_i$,表示在 $(i,p_i)$ 处有一个颜色为 $c_i$ 的点。

接下来 $q$ 行,每行四个整数 $l,r,d,u$,表示求满足 $l \leq i \leq r,d \leq p_i \leq u$ 的点的颜色数。

输出格式

$q$ 行,第 $i$ 行一个整数,表示第 $i$ 次询问的答案。

数据范围与约定

对于所有测试点,满足 $1 \leq n \leq 10^5,q = n,1 \leq c_i \leq n,1 \leq l \leq r \leq n,1 \leq d \leq u \leq n$,同时保证 $p$ 是一个长为 $n$ 的排列。

如果没有特殊说明,子任务空间限制为 1024M。

子任务 $n \leq$ 特殊性质 分值
$1$ $10^3$ $10$
$2$ $8 \times 10^4$ $20$
$3$ $9\times 10^4$ $20$
$4$ $10^5$ $20$
$5$ $10^5$ 只有不超过 $100$ 种颜色 $10$
$6$ $10^5$ 每种颜色的点的个数不超过 $3$ $10$
$7$ $10^5$ 空间限制为 64MB $10$