#1850. 「NOI2020」时代的眼泪

「NOI2020」时代的眼泪

题目描述

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

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

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

更具体地,智者给定了 nn 个事件,他们用平面上 nn不同的点 {(xi,yi)}i=1n\{(x_i,y_i)\}^n_{i =1} 来表示;

智者还给定了 mm时代,每个时代用平面上一个矩形 (ri,1,ri,2,ci,1,ci,2)(r_{i,1}, r_{i,2}, c_{i,1}, c_{i,2}) 来表示,其中 (ri,1,ci,1)(r_{i,1}, c_{i,1}) 是矩形的左下角,(ri,2,ci,2)(r_{i,2}, c_{i,2}) 是矩形的右上角,保证 (ri,1,ci,1)(ri,2,ci,2)(r_{i,1}, c_{i, 1}) \le (r_{i,2}, c_{i,2})。我们称时代 ii 包含了事件 jj 当且仅当 $(r_{i,1}, c_{i,1})\le (x_j, y_j)\le (r_{i,2}, c_{i,2})$。

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

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

输入格式

从文件 tears.in 中读入数据。

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

第二行 nn 个整数 pip_i,其中第 ii 个数表示事件 ii 在平面上的坐标为 (i,pi)(i, p_i)。保证 pip_i 为一个 11nn 的排列。

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

输出格式

输出到文件 tears.out 中。

输出 mm 行,每行包含一个整数,第 ii 行输出第 ii 个时代的眼泪的大小。

样例

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

对于时代 11,包含的遗憾有 (6,7)(6, 7)(即事件 66 与事件 77 形成的遗憾,下同)。

对于时代 22,包含的遗憾有 (5,6),(6,7),(5,7),(5,8)(5, 6), (6, 7), (5, 7), (5, 8)

对于时代 33,包含的遗憾有 (5,6),(5,8)(5, 6), (5, 8)

对于时代 44,包含的遗憾有 (5,6),(6,7),(5,7),(5,8)(5, 6), (6, 7), (5, 7), (5, 8)

对于时代 55,包含的遗憾有 (5,6),(6,7),(5,7),(5,8)(5, 6), (6, 7), (5, 7), (5, 8)

对于时代 66,包含的遗憾有 (5,6),(6,7),(5,7),(5,8)(5, 6), (6, 7), (5, 7), (5, 8)

对于时代 7,8,97, 8, 9,它们均不包含任何遗憾。

见下发文件中的 tears2.intears2.ans

该样例满足特殊限制 A(具体限制见测试点约束)。

见下发文件中的 tears3.intears3.ans

该样例满足特殊限制 B(具体限制见测试点约束)。

数据范围与提示

对于所有测试点:1n1051\le n\le 10^51m2×1051\le m\le 2\times 10^51ri,1,ri,2,ci,1,ci,2n1\le r_{i,1}, r_{i,2}, c_{i,1}, c_{i,2}\le n

每个测试点的具体限制见下表:

测试点编号 nn\le mm\le 特殊性质
131\sim3 1010
44 3,0003,000
55 4,0004,000
66 5,0005,000
77 25,00025,000 50,00050,000 A
88 50,00050,000 100,000100,000
99 75,00075,000 150,000150,000
1010 100,000100,000 200,000200,000
1111 60,00060,000 120,000120,000 B
1212 80,00080,000 160,000160,000
1313 100,000100,000 200,000200,000
1414 20,00020,000 40,00040,000
1515 30,00030,000 60,00060,000
1616 40,00040,000 80,00080,000
1717 50,00050,000 100,000100,000
1818 60,00060,000 120,000120,000
1919 70,00070,000 140,000140,000
202220\sim 22 100,000100,000 200,000200,000 C
232523\sim25

特殊限制 A:对于所有时代 iici,1=1,ci,2=nc_{i,1} = 1, c_{i,2} = n

特殊限制 B:任意两个不同时代所代表的矩形,它们要么是包含关系(一个矩形在另一个矩形内,边界允许重合),要么是相离关系(两矩形不包含共同点,边界不允许重合)。

特殊限制 C:最多有 5050 对事件 (i,j)(i, j)1i<jn1\le i < j\le n不满足 (i,pi)(j,pj)(i, p_i)\le (j, p_j)