{"problem":{"name":"C. Boredom","description":{"content":"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","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF853C"},"statements":[{"statement_type":"Markdown","content":"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.\n\nFirst 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.\n\nIlya 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.\n\nNow 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.\n\n## Input\n\nThe first line of input contains two integers _n_ and _q_ (2 ≤ _n_ ≤ 200 000, 1 ≤ _q_ ≤ 200 000) — the size of the grid and the number of query rectangles.\n\nThe 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.\n\nThe 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.\n\n## Output\n\nFor each query rectangle output its beauty degree on a separate line.\n\n[samples]\n\n## Note\n\nThe first sample test has one beautiful rectangle that occupies the whole grid, therefore the answer to any query is 1.\n\nIn the second sample test the first query rectangle intersects 3 beautiful rectangles, as shown on the picture below:\n\n![image](https://espresso.codeforces.com/ab1c66ff4bb212f2eaa1df6a3126acc2bc79535c.png) ![image](https://espresso.codeforces.com/e4576fb30a1da895a09193faaf3d92ff2bf16cc9.png) ![image](https://espresso.codeforces.com/3d67c946457a83004c99989b9ccf062d66affd1f.png)\n\nThere are 5 beautiful rectangles that intersect the second query rectangle, as shown on the following picture:\n\n![image](https://espresso.codeforces.com/56bf16b394d5a08e28d2fd8d5ad57392f1cc10e0.png) ![image](https://espresso.codeforces.com/c7d7961cd0d50c64b5a1ec104f16bc95254199a2.png) ![image](https://espresso.codeforces.com/fa6096a3000f51ae6f1d798801441540454f6b9f.png) ![image](https://espresso.codeforces.com/c87e98c04601ad2d95d654f7f31371198d98d1d6.png) ![image](https://espresso.codeforces.com/cab8b66423587e485b08708148a8ce2194ac9558.png)","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"[{\"iden\":\"statement\",\"content\":\"Ilya 正坐在莫斯科机场的候机区，厌倦了不断显示他的航班延误的时刻表。于是他拿出一张纸，决定解决一些问题。\\n\\n首先，Ilya 画了一个大小为 $n × n$ 的网格，并在上面标记了 $n$ 个格子，使得任意两个标记的格子不在同一行或同一列。他将网格上边与网格边平行的矩形称为 _美丽矩形_，当且仅当该矩形的四个角中恰好有两个是标记的格子。恰好有 $n·(n - 1) / 2$ 个美丽矩形。\\n\\nIlya 在网格上选择了 $q$ 个边与网格边平行的查询矩形（不一定是美丽矩形），对于每个查询矩形，他希望求出其 _美丽度_。一个矩形的美丽度定义为：与其至少共享一个格子的美丽矩形的数量。\\n\\n现在 Ilya 认为他可能没有足够的时间在航班起飞前解决这个问题。你得到了标记格子的描述和查询矩形的信息，请帮助 Ilya 求出每个查询矩形的美丽度。\\n\\n输入的第一行包含两个整数 $n$ 和 $q$（$2 ≤ n ≤ 200 000$，$1 ≤ q ≤ 200 000$）——网格的大小和查询矩形的数量。\\n\\n第二行包含 $n$ 个整数 $p_1, p_2, ..., p_n$，用空格分隔（$1 ≤ p_i ≤ n$，所有 $p_i$ 互不相同），它们指定了 Ilya 标记的格子：在第 $i$ 列，他在第 $p_i$ 行标记了一个格子。行从 $1$ 到 $n$ 从下到上编号，列从 $1$ 到 $n$ 从左到右编号。\\n\\n接下来的 $q$ 行描述查询矩形。每个矩形由四个整数 $l, d, r, u$ 描述（$1 ≤ l ≤ r ≤ n$，$1 ≤ d ≤ u ≤ n$），其中 $l$ 和 $r$ 是矩形的最左列和最右列，$d$ 和 $u$ 是矩形的最底行和最顶行。\\n\\n对于每个查询矩形，在单独一行输出其美丽度。\\n\\n第一个样例测试中有一个美丽矩形占据了整个网格，因此任何查询的答案都是 1。\\n\\n在第二个样例测试中，第一个查询矩形与 3 个美丽矩形相交，如下图所示：\\n\\n  \\n\\n第二个查询矩形与 5 个美丽矩形相交，如下图所示：\\n\\n    \\n\\n\"},{\"iden\":\"input\",\"content\":\"输入的第一行包含两个整数 $n$ 和 $q$（$2 ≤ n ≤ 200 000$，$1 ≤ q ≤ 200 000$）——网格的大小和查询矩形的数量。第二行包含 $n$ 个整数 $p_1, p_2, ..., p_n$，用空格分隔（$1 ≤ p_i ≤ n$，所有 $p_i$ 互不相同），它们指定了 Ilya 标记的格子：在第 $i$ 列，他在第 $p_i$ 行标记了一个格子。行从 $1$ 到 $n$ 从下到上编号，列从 $1$ 到 $n$ 从左到右编号。接下来的 $q$ 行描述查询矩形。每个矩形由四个整数 $l, d, r, u$ 描述（$1 ≤ l ≤ r ≤ n$，$1 ≤ d ≤ u ≤ n$），其中 $l$ 和 $r$ 是矩形的最左列和最右列，$d$ 和 $u$ 是矩形的最底行和最顶行。\"},{\"iden\":\"output\",\"content\":\"对于每个查询矩形，在单独一行输出其美丽度。\"},{\"iden\":\"examples\",\"content\":\"输入：\\n2 3\\n1 2\\n1 1 1 1\\n1 1 1 2\\n1 1 2 2\\n\\n输出：\\n1\\n1\\n1\\n\\n输入：\\n4 2\\n1 3 2 4\\n4 1 4 4\\n1 1 2 3\\n\\n输出：\\n3\\n5\"},{\"iden\":\"note\",\"content\":\"第一个样例测试中有一个美丽矩形占据了整个网格，因此任何查询的答案都是 1。在第二个样例测试中，第一个查询矩形与 3 个美丽矩形相交，如下图所示：  第二个查询矩形与 5 个美丽矩形相交，如下图所示：    \"}]}","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let the set of marked cells be $ M = \\{ (p_i, i) \\mid i = 1, 2, \\dots, n \\} $, where $ p_i $ is the row index of the marked cell in column $ i $, with rows numbered bottom to top (1 to $ n $) and columns left to right (1 to $ n $).\n\nA rectangle is *beautiful* if it has exactly two marked corners, i.e., it is defined by two distinct marked points $ (p_i, i) $ and $ (p_j, j) $ with $ i \\ne j $, and its corners are exactly these two points (opposite corners of the axis-aligned rectangle they define). The number of such rectangles is $ \\binom{n}{2} = \\frac{n(n-1)}{2} $.\n\nLet $ R = [l, r] \\times [d, u] $ denote a query rectangle with column range $ [l, r] $ and row range $ [d, u] $.\n\nThe *beauty degree* of $ R $ is the number of beautiful rectangles that share at least one grid square with $ R $.\n\n---\n\n### Formal Problem Statement:\n\n**Given:**\n- $ n \\in \\mathbb{N} $, $ q \\in \\mathbb{N} $, with $ 2 \\leq n \\leq 200{,}000 $, $ 1 \\leq q \\leq 200{,}000 $.\n- A permutation $ p = (p_1, p_2, \\dots, p_n) \\in \\{1, 2, \\dots, n\\}^n $, where $ p_i $ is the row of the marked cell in column $ i $.\n- $ q $ query rectangles, each defined by $ (l, d, r, u) $, with $ 1 \\leq l \\leq r \\leq n $, $ 1 \\leq d \\leq u \\leq n $.\n\n**Define:**\n- Let $ \\mathcal{B} = \\{ B_{ij} \\mid 1 \\leq i < j \\leq n \\} $, where $ B_{ij} $ is the axis-aligned rectangle with opposite corners at $ (p_i, i) $ and $ (p_j, j) $.  \n  (Each $ B_{ij} $ is uniquely determined by the pair $ (i,j) $, and has corners: $ (\\min(p_i,p_j), \\min(i,j)) $, $ (\\max(p_i,p_j), \\max(i,j)) $.)\n\n- A beautiful rectangle $ B_{ij} $ *intersects* the query rectangle $ R = [l, r] \\times [d, u] $ if:\n  $$\n  [l, r] \\cap [\\min(i,j), \\max(i,j)] \\neq \\emptyset \\quad \\text{and} \\quad [d, u] \\cap [\\min(p_i,p_j), \\max(p_i,p_j)] \\neq \\emptyset\n  $$\n\n**Objective:**\nFor each query rectangle $ R = [l, r] \\times [d, u] $, compute:\n$$\n\\left| \\left\\{ (i,j) \\mid 1 \\leq i < j \\leq n, \\; B_{ij} \\cap R \\neq \\emptyset \\right\\} \\right|\n$$\n\n---\n\n### Equivalent Reformulation (for efficient computation):\n\nLet $ A = \\{ (i, p_i) \\mid i = 1, \\dots, n \\} $. For each unordered pair $ \\{ (i, p_i), (j, p_j) \\} $, define rectangle $ R_{ij} $ as the minimal axis-aligned rectangle containing both points.\n\nWe want, for each query $ Q = [l, r] \\times [d, u] $, to count the number of pairs $ (i,j) $, $ i < j $, such that:\n$$\n[\\min(i,j), \\max(i,j)] \\cap [l, r] \\neq \\emptyset \\quad \\text{and} \\quad [\\min(p_i,p_j), \\max(p_i,p_j)] \\cap [d, u] \\neq \\emptyset\n$$\n\nThis is equivalent to counting all pairs $ (i,j) $ such that:\n- The column interval of $ R_{ij} $ overlaps with $ [l, r] $, **and**\n- The row interval of $ R_{ij} $ overlaps with $ [d, u] $.\n\nThus, the beauty degree is:\n$$\n\\boxed{\n\\left| \\left\\{ (i,j) \\in \\binom{[n]}{2} \\;\\middle|\\; [\\min(i,j), \\max(i,j)] \\cap [l, r] \\neq \\emptyset \\;\\land\\; [\\min(p_i,p_j), \\max(p_i,p_j)] \\cap [d, u] \\neq \\emptyset \\right\\} \\right|\n}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF853C","tags":["data structures"],"sample_group":[["2 3\n1 2\n1 1 1 1\n1 1 1 2\n1 1 2 2","1\n1\n1"],["4 2\n1 3 2 4\n4 1 4 4\n1 1 2 3","3\n5"]],"created_at":"2026-03-03 11:00:39"}}