P6774 [NOI2020] Tears of the Times.

Xiao L likes to communicate and discuss with wise people, and the wise person often gives Xiao L some thinking problems. Today the wise person came up with another problem for Xiao L. The wise person first abstracted space-time into a two-dimensional plane, then abstracted an event as a point on this plane, and abstracted an era as a rectangle on this plane. For convenience, let $(a, b) \leq (c, d)$ denote that two points $(a, b)$ and $(c, d)$ on the plane satisfy $a \leq c$ and $b \leq d$. More specifically, the wise person is given $n$ **events**, represented by $n$ distinct points $\{(x_i, y_i)\}^n_{i=1}$ on the plane. The wise person is also given $m$ **eras**, each represented by a rectangle $(r_{i,1}, r_{i,2}, c_{i,1}, c_{i,2})$ on the plane, where $(r_{i,1}, c_{i,1})$ is the lower-left corner and $(r_{i,2}, c_{i,2})$ is the upper-right corner. It is guaranteed that $(r_{i,1}, c_{i,1}) \leq (r_{i,2}, c_{i,2})$. We say that era $i$ contains event $j$ if and only if $(r_{i,1}, c_{i,1}) \leq (x_j, y_j) \leq (r_{i,2}, c_{i,2})$. The wise person believes that if two events $i, j$ satisfy $(x_i, y_i) \leq (x_j, y_j)$, then these two events form a **regret**. For all events contained in an era, the regrets formed by them are called the **tears of this era**, and the number of regrets is called the size of the tears of this era. Now the wise person wants Xiao L to compute **the size of the tears for each era**. Xiao L understands that if he cannot answer this question, he will also become tears of the times. Please help him.

Read from standard input. The first line contains two integers $n, m$, representing the number of events and the number of eras. The second line contains $n$ integers $p_i$, where the $i$-th number means that event $i$ has coordinates $(i, p_i)$ on the plane. It is guaranteed that $p_i$ is a permutation of $1$ to $n$. Then follow $m$ lines, each containing four integers $r_{i,1}, r_{i,2}, c_{i,1}, c_{i,2}$, representing the rectangle corresponding to each era.

Output to standard output. Output $m$ lines, each containing one integer. On the $i$-th line, output the size of the tears of the $i$-th era.

#### Explanation for Sample 1 For era $1$, the regret it contains is $(6, 7)$ (that is, the regret formed by events $6$ and $7$, same below). For era $2$, the regrets it contains are $(5, 6), (6, 7), (5, 7), (5, 8)$. For era $3$, the regrets it contains are $(5, 6), (5, 8)$. For era $4$, the regrets it contains are $(5, 6), (6, 7), (5, 7), (5, 8)$. For era $5$, the regrets it contains are $(5, 6), (6, 7), (5, 7), (5, 8)$. For era $6$, the regrets it contains are $(5, 6), (6, 7), (5, 7), (5, 8)$. For eras $7, 8, 9$, none of them contains any regret. #### Sample 2 See tears/tears2.in and tears/tears2.ans in the contestant directory. This sample satisfies Special Constraint A (see test point constraints for details). #### Sample 3 See tears/tears3.in and tears/tears3.ans in the contestant directory. This sample satisfies Special Constraint B (see test point constraints for details). For all test points: $1 \leq n \leq 10^5$, $1 \leq m \leq 2 \times 10^5$, $1 \leq r_{i,1}, r_{i,2}, c_{i,1}, c_{i,2} \leq n$. --- ### Test Point Constraints The specific limits for each test point are shown in the table below: | Test Point ID | $n\le $ | $m\le $ | Special Constraint | | :-: | :-: | :-: | :-: | | $1\sim 3$ | $10$ | $10$ | None | | $4$ | $3\times 10^3$ | $3\times 10^3$ | None | | $5$ | $4\times 10^3$ | $4\times 10^3$ | None | | $6$ | $5\times 10^3$ | $5\times 10^3$ | None | | $7$ | $2.5\times 10^4$ | $5\times 10^4$ | $\text{A}$ | | $8$ | $5\times 10^4$ | $10^5$ | $\text{A}$ | | $9$ | $7.5\times 10^4$ | $1.5\times 10^5$ | $\text{A}$ | | $10$ | $10^5$ | $2\times 10^5$ | $\text{A}$ | | $11$ | $6\times 10^4$ | $1.2\times 10^5$ | $\text{B}$ | | $12$ | $8\times 10^4$ | $1.6\times 10^5$ | $\text{B}$ | | $13$ | $10^5$ | $2\times 10^5$ | $\text{B}$ | | $14$ | $2\times 10^4$ | $4\times 10^4$ | None | | $15$ | $3\times 10^4$ | $6\times 10^4$ | None | | $16$ | $4\times 10^4$ | $8\times 10^4$ | None | | $17$ | $5\times 10^4$ | $10^5$ | None | | $18$ | $6\times 10^4$ | $1.2\times 10^5$ | None | | $19$ | $7\times 10^4$ | $1.4\times 10^5$ | None | | $20\sim 22$ | $10^5$ | $2\times 10^5$ | $\text{C}$ | | $23\sim 25$ | $10^5$ | $2\times 10^5$ | None | Special Constraint A: For all eras $i$, we have $c_{i,1} = 1$ and $c_{i,2} = n$. Special Constraint B: For any two different eras, the rectangles they represent are either in a containment relationship (one rectangle is inside the other; boundaries may overlap) or are disjoint (the two rectangles share no common point; boundaries are not allowed to touch). Special Constraint C: There are at most $50$ pairs of events $(i, j)(1 \leq i < j \leq n)$ that do not satisfy $(i, p_i) \leq (j, p_j)$. Translated by ChatGPT 5