Boredom

题意翻译

### 题意 给定一个$\ n*n(1\leq n\leq 200,000)\ $的矩阵$A$，矩阵所在的直角坐标系以向上、向右为正方向。 从 $A$ 的第 $i$ 行中选出第$s_i$个格子标记为黑色,保证被选中的 $n$ 个格子不在同一列 再给定该矩阵的一个子矩阵 $B$ $B$ 的**左、右**边界横坐标分别为$l,r$,**下、上**边界纵坐标分别为$d,u(1\leq l\leq r\leq n,1\leq d\leq u\leq n)$. 请你回答:有几个好的矩阵与 $B$ 相交？ 会有 $T(1\leq T\leq 200,000)$ 组离线询问. 我们称一个矩阵为好的矩阵，当且仅当该矩阵至少存在一条对角线使其两个端点上的格子为黑色格子。 ### 输入格式 ``` n T s_1 s_2 s_3...s_n l_1 d_1 r_1 u_1 l_2 d_2 r_2 u_2 l_3 d_3 r_3 u_3 ... l_T d_T r_T u_T ``` ### 输出格式 $T$ 行, 每行一个数表示答案。

题目描述

Ilya is sitting in a waiting area of Metropolis airport and is bored of looking at time table that shows again and again that his plane is delayed. So he took out a sheet of paper and decided to solve some problems. First Ilya has drawn a grid of size $ n×n $ and marked $ n $ squares on it, such that no two marked squares share the same row or the same column. He calls a rectangle on a grid with sides parallel to grid sides beautiful if exactly two of its corner squares are marked. There are exactly $ n·(n-1)/2 $ beautiful rectangles. Ilya has chosen $ q $ query rectangles on a grid with sides parallel to grid sides (not necessarily beautiful ones), and for each of those rectangles he wants to find its beauty degree. Beauty degree of a rectangle is the number of beautiful rectangles that share at least one square with the given one. Now Ilya thinks that he might not have enough time to solve the problem till the departure of his flight. You are given the description of marked cells and the query rectangles, help Ilya find the beauty degree of each of the query rectangles.

输入输出格式

输入格式

The first line of input contains two integers $ n $ and $ q $ ( $ 2<=n<=200000 $ , $ 1<=q<=200000 $ ) — the size of the grid and the number of query rectangles. The second line contains $ n $ integers $ p_{1},p_{2},...,p_{n} $ , separated by spaces ( $ 1<=p_{i}<=n $ , all $ p_{i} $ are different), they specify grid squares marked by Ilya: in column $ i $ he has marked a square at row $ p_{i} $ , rows are numbered from $ 1 $ to $ n $ , bottom to top, columns are numbered from $ 1 $ to $ n $ , left to right. The following $ q $ lines describe query rectangles. Each rectangle is described by four integers: $ l,d,r,u $ ( $ 1<=l<=r<=n $ , $ 1<=d<=u<=n $ ), here $ l $ and $ r $ are the leftmost and the rightmost columns of the rectangle, $ d $ and $ u $ the bottommost and the topmost rows of the rectangle.

输出格式

For each query rectangle output its beauty degree on a separate line.

输入输出样例

输入样例 #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

说明

The first sample test has one beautiful rectangle that occupies the whole grid, therefore the answer to any query is 1. In the second sample test the first query rectangle intersects 3 beautiful rectangles, as shown on the picture below:  There are 5 beautiful rectangles that intersect the second query rectangle, as shown on the following picture: 

题意翻译

### 题意 给定一个$\ n*n(1\leq n\leq 200,000)\ $的矩阵$A$，矩阵所在的直角坐标系以向上、向右为正方向。 从 $A$ 的第 $i$ 行中选出第$s_i$个格子标记为黑色,保证被选中的 $n$ 个格子不在同一列 再给定该矩阵的一个子矩阵 $B$ $B$ 的**左、右**边界横坐标分别为$l,r$,**下、上**边界纵坐标分别为$d,u(1\leq l\leq r\leq n,1\leq d\leq u\leq n)$. 请你回答:有几个好的矩阵与 $B$ 相交？ 会有 $T(1\leq T\leq 200,000)$ 组离线询问. 我们称一个矩阵为好的矩阵，当且仅当该矩阵至少存在一条对角线使其两个端点上的格子为黑色格子。 ### 输入格式 ``` n T s_1 s_2 s_3...s_n l_1 d_1 r_1 u_1 l_2 d_2 r_2 u_2 l_3 d_3 r_3 u_3 ... l_T d_T r_T u_T ``` ### 输出格式 $T$ 行, 每行一个数表示答案。