小 L 喜欢与智者交流讨论，而智者也经常为小 L 出些思考题。

\n

这天智者又为小 L 构思了一个问题。智者首先将时空抽象为了一个二维平面，进而将一个事件抽象为该平面上的一个点，将一个时代抽象为该平面上的一个矩形。

\n

为了方便，下面记 $(a,b) \\le (c,d)$ 表示平面上两个点 $(a,b),(c,d)$ 满足 $a \\le c,b \\le d$。

\n

更具体地，智者给定了 $n$ 个事件，他们用平面上 n 个不同的点 $\\{(x_i,y_i)\\}^{n}_{i=1}$ 来表示；智者还给定了 $m$ 个时代，每个时代用平面上一个矩形 $(r_{i,1},r_{i,2},c_{i,1},c_{i,2})$ 来表示，其中 $(r_{i,1},c_{i,1})$ 是矩形的左下角，$(r_{i,2},c_{i,2})$ 是矩形的右上角，保证 $(r_{i,1},c_{i,1}) \\le (r_{i,2},c_{i,2})$。我们称时代 $i$ 包含了事件 $j$ 当且仅当 $(r_{i,1},c_{i,1}) \\le (x_j,y_j) \\le (r_{i,2},c_{i,2})$。

\n

智者认为若两个事件 $i,j$ 满足 $(x_i,y_i) \\le (x_j,y_j)$，则这两个事件形成了一次遗憾。而对一个时代内包含的所有事件，它们所形成的遗憾被称为这个时代的眼泪，而形成的遗憾次数则称为该时代的眼泪的大小。现在智者想要小 L 计算每个时代的眼泪的大小 。

\n

小 L 明白，如果他回答不了这个问题，他也将成为时代的眼泪，请你帮帮他。

\n

输出格式

\n

第一行两个整数 $n,m$，分别表示事件数与时代数。

\n

第二行 $n$ 个整数 $p_i$，其中第 $i$ 个数表示事件 $i$ 在平面上的坐标为 $(i,p_i$)。保证 $p_i$ 为一个 $1$ 到 $n$ 的排列。

\n

之后 $m$ 行，每行四个整数 $r_{i,1},r_{i,2},c_{i,1},c_{i,2}$，表示每个时代对应的矩形。

\n

输出格式

\n

输出 $m$ 行，每行包含一个整数，第 $i$ 行输出第 $i$ 个时代的眼泪的大小。

\n\n\n

统计

递交统计

【NOI2020】时代的眼泪

信息

状态

开发

支持

还没有账户？

登录