不知道咋改空间限制,所以最后一个子任务开的是 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$ |