← 返回题目列表

Codeforces · 853/C

C. 无聊

中文机器翻译题面 查看原题

伊利亚(Ilya)坐在大都会机场的候机区,厌倦了查看一次又一次显示他的飞机延误的时刻表。于是他拿出一张纸,决定解决一些问题。

首先,Ilya 绘制了一个大小为 n × n 的网格,并在其上标记了 n 个方块,使得没有两个标记的方块共享同一行或同一列。如果网格上的边与网格边平行的矩形恰好有两个角正方形被标记,他称该矩形是美丽的。正好有 n·(n - 1) / 2 个漂亮的矩形。

Ilya 在网格上选择了 q 个查询矩形,其边与网格边平行(不一定是漂亮的),并且对于每个矩形,他想找到其美丽程度。矩形的美度是指与给定矩形至少共享一个正方形的漂亮矩形的数量。

现在Ilya认为他可能没有足够的时间来解决这个问题,直到他的航班起飞。给你标记单元格和查询矩形的描述,帮助Ilya找出每个查询矩形的美观程度。

输入

输入的第一行包含两个整数 n 和 q (2 ≤ n ≤ 200 000, 1 ≤ q ≤ 200 000) - 网格的大小和查询矩形的数量。

第二行包含 n 个整数 p1, p2, ..., pn,用空格分隔(1 ≤ pi ≤ n,所有 pi 都不同),它们指定由 Ilya 标记的网格方块:在第 i 列中,他在 pi 行标记了一个方块,行从 1 到 n 编号,从下到上,列从 1 到 n 编号,从左到右。

以下 q 行描述查询矩形。每个矩形由四个整数描述:l、d、r、u(1 ≤ l ≤ r ≤ n,1 ≤ d ≤ u ≤ n),其中l和r是矩形的最左和最右列,d和u是矩形的最底和最顶行。

输出

对于每个查询矩形,在单独的行上输出其美丽程度。

示例

输入 #1

2 3
1 2
1 1 1 1
1 1 1 2
1 1 2 2

输出 #1

1
1
1

输入 #2

4 2
1 3 2 4
4 1 4 4
1 1 2 3

输出 #2

3
5

注意

第一个样本测试有一个漂亮的矩形占据了整个网格,因此任何查询的答案都是 1。

在第二个示例测试中,第一个查询矩形与3个漂亮的矩形相交,如下图所示:

有5个漂亮的矩形与第二个查询矩形相交,如下图所示: