Happy Sugar Life - 题目

砂糖和盐给你一个二维平面，记平面上两个点 $(x_1,y_1),(x_2,y_2)$ 构成支配对（记为$(x_1,y_1)\le (x_2,y_2)$）当且仅当 $x_1\le x_2,\;y_1\le y_2$。平面上初始给定 $n$ 个不同的点 $\{(x_i,y_i)\}_{i=1}^n$。

你需要回答 $m$ 次询问，每次询问给出两个点 $(x,y),(x',y')$，问有多少二元组 $(i,j)$ 满足 $(x,y)\le (x_i,y_i)\le (x_j,y_j)\le (x',y')$ 且 $i \neq j$。

输入格式

第一行两个数 $n,m$。

第二行 $n$ 个数，其中第 $i$ 个数 $p_i$ 表示平面上初始给定的第 $i$ 个点 $(i,p_i)$，保证 $p_i$ 为一个 $1$ 到 $n$ 的排列。

之后 $m$ 行，每行用四个空格隔开的数，分别表示 $x,x',y,y'$，表示一次询问，保证 $(x,y)\le (x',y')$。

输出格式

输出 $m$ 行，第 $i$ 行输出一行一个整数，表示第 $i$ 次询问的答案。

样例数据

样例输入

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

样例输出

样例解释

对于第一次询问，可以发现满足 $(x,y)\le (x_i,y_i)\le (x',y')$ 的 $(x_i,y_i)$ 有 $(4,6),(6,4),(7,5),(8,3)$，支配对有 $(6,4),(7,5)$，所对应的二元组为 $(6,7)$。

对于第二次询问，可以发现满足 $(x,y)\le (x_i,y_i)\le (x',y')$ 的 $(x_i,y_i)$ 有 $(2,8),(3,7),(4,6),(5,2),(6,4),(7,5),(8,3),(9,1)$，支配对有 $(5,2),(6,4)$ 和 $(6,4),(7,5)$ 和 $(5,2),(7,5)$ 和 $(5,2),(8,3)$，所对应的二元组为 $(5,6),(6,7),(5,7),(5,8)$。

对于第三次询问，可以发现满足$(x,y)\le (x_i,y_i)\le (x',y')$ 的 $(x_i,y_i)$ 有 $(5,2),(6,4),(8,3)$，支配对有 $(5,2),(6,4)$ 和 $(5,2),(8,3)$，所对应的二元组为 $(5,6),(5,8)$。

对于第四次询问，可以发现满足$(x,y)\le (x_i,y_i)\le (x',y')$ 的 $(x_i,y_i)$ 有 $(4,6),(5,2),(6,4),(7,5),(8,3)$，支配对有 $(5,2),(6,4)$ 和 $(6,4),(7,5)$ 和 $(5,2),(7,5)$ 和 $(5,2),(8,3)$，所对应的二元组为 $(5,6),(6,7),(5,7),(5,8)$。

对于第五次询问，可以发现满足 $(x,y)\le (x_i,y_i)\le (x',y')$ 的 $(x_i,y_i)$ 有 $(4,6),(5,2),(6,4),(7,5),(8,3)$，支配对有 $(5,2),(6,4)$ 和 $(6,4),(7,5)$ 和 $(5,2),(7,5)$ 和 $(5,2),(8,3)$，所对应的二元组为 $(5,6),(6,7),(5,7),(5,8)$。

对于第六次询问，可以发现满足 $(x,y)\le (x_i,y_i)\le (x',y')$ 的 $(x_i,y_i)$ 有 $(1,9),(2,8),(3,7),(4,6),(5,2),(6,4),(7,5),(8,3),(9,1)$，支配对有 $(5,2),(6,4)$ 和 $(6,4),(7,5)$ 和 $(5,2),(7,5)$ 和 $(5,2),(8,3)$，所对应的二元组为 $(5,6),(6,7),(5,7),(5,8)$。

对于第七次询问，可以发现满足 $(x,y)\le (x_i,y_i)\le (x',y')$ 的 $(x_i,y_i)$ 有 $(3,7)$，无支配对。

对于第八次询问，可以发现无满足 $(x,y)\le (x_i,y_i)\le (x',y')$ 的 $(x_i,y_i)$，无支配对。

对于第九次询问，可以发现无满足 $(x,y)\le (x_i,y_i)\le (x',y')$ 的 $(x_i,y_i)$，无支配对。

子任务

Idea：ccz181078&nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：nzhtl1477&ccz181078

对于 $100 \%$ 的数据，$1 \le n \le 10^5$，$1 \le m \le 2 \times 10^5$。

QOJ.ac

QOJ