#P17689. [Ynoi2019] Happy Sugar Life

    ID: 16673 传统题 4000ms 128MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600分块树状数组数据结构前缀和算法基础数学

[Ynoi2019] Happy Sugar Life

题目描述

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

你需要回答 mm 次询问,每次询问给出两个点 (x,y),(x′,y′)(x,y),(x',y'),问有多少二元组 (i,j)(i,j) 满足 (x,y)≤(xi,yi)≤(xj,yj)≤(x′,y′)(x,y)\le (x_i,y_i)\le (x_j,y_j)\le (x',y') 且 i≠ji \neq j。

输入格式

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

第二行 nn 个数,其中第 ii 个数 pip_i 表示平面上初始给定的第 ii 个点 (i,pi)(i,p_i),保证 pip_i 为一个 11 到 nn 的排列。

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

输出格式

输出 mm 行,第 ii 行输出一行一个整数,表示第 ii 次询问的答案。

输入输出样例 #1

输入 #1

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

1
4
2
4
4
4
0
0
0

说明/提示

Idea:ccz181078&nzhtl1477,Solution:ccz181078,Code:ccz181078,Data:nzhtl1477&ccz181078

对于 100%100 \% 的数据,1≤n≤1051 \le n \le 10^5,1≤m≤2×1051 \le m \le 2 \times 10^5。

样例解释

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

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

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

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

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

对于第六次询问,可以发现满足 (x,y)≤(xi,yi)≤(x′,y′)(x,y)\le (x_i,y_i)\le (x',y') 的 (xi,yi)(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)(5,2),(6,4) 和 (6,4),(7,5)(6,4),(7,5) 和 (5,2),(7,5)(5,2),(7,5) 和 (5,2),(8,3)(5,2),(8,3),所对应的二元组为 (5,6),(6,7),(5,7),(5,8)(5,6),(6,7),(5,7),(5,8)。

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

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

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