[Ynoi2019] Happy Sugar Life

我不曾明白—— 所谓温暖是什么样的感觉？ 所谓温柔的是什么？ 所谓的怜爱是什么？  更重要的是…… 我不能理解什么是“爱” 但是，现在我明白了—— 我终于明白了爱的真正含义  ——这份闪闪发光的感情，就是爱吧 我发誓—— 无论疾病还是健康 无论高兴还是悲伤 无论富有还是贫穷 直到死亡为止 我将砂糖视为最爱，至死分离  我从前没有爱过人 被人咬耳朵告白这种事—— 倒是发生过许多次 但是，无论是甜言蜜语 还是做了什么事情 我都无法感受到  砂糖酱，痛吗 ——我没事，不过……不能前往新的城堡了 ——对不起 没事 果然我还是和砂糖酱在一起的时候最幸福了 ——小盐……  呐，砂糖酱，我思考过—— 那个时候，被妈妈抛弃的时候 我大概是死掉的状态 又悲伤，又痛苦 觉得一切都无所谓，世界一片空白—— 但是砂糖酱出现了 遇到砂糖，一起生活，过得很幸福 ——我也是哦，小盐  所以，我想要和砂糖酱在一起 想要和砂糖一起幸福到最后 所以，我们一起死吧，砂糖！ ——小盐……  我原本都不知道 温暖是何种感受 温柔是何物 慈爱又是什么 最重要的是 我曾无法理解“爱”是什么 这多亏了小盐 因为那时小盐抓住了我的手 因为小盐为我指引道路 我才明白有生以来从未感受过的幸福的意义 我一直都不明白 原来教会我什么是爱的 也是小盐 小盐，转世之后也要对我告白哦 对不起 谢谢你  这就是我的 $\texttt {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

1
4
2
4
4
4
0
0
0

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$。 #### 样例解释 对于第一次询问，可以发现满足 $(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)$，无支配对。