P6579 [Ynoi2019] Happy Sugar Life

I never understood— What does “warmth” feel like? What is “gentleness”? What is “cherishing”?  More importantly… I cannot understand what “love” is. But now, I understand— I finally understand the true meaning of love.  —This shining feeling is probably love. I swear— Whether in sickness or in health, Whether in happiness or in sorrow, Whether rich or poor, Until death, I will regard Satou as my dearest, never parting until death.  I had never loved anyone before. Being confessed to by someone whispering in my ear— That has happened many times. But, whether it was sweet talk, Or whatever they did, I could not feel anything.  Satou-chan, does it hurt? —I’m fine, but… I can’t go to a new castle anymore. —I’m sorry. It’s fine. After all, I am happiest when I’m with Satou-chan. —Shio…  Hey, Satou-chan, I’ve thought about it— Back then, when I was abandoned by mom, I was probably already like I was dead. Sad and painful, Feeling like nothing mattered, the world was completely blank— But then Satou-chan appeared. Meeting Satou, living together, being very happy. —Me too, Shio.  So, I want to be with Satou-chan. I want to be happy with Satou until the end. So, let’s die together, Satou! —Shio…  I originally didn’t know What warmth feels like, What gentleness is, Or what kindness is. Most importantly, I could not understand what “love” was. This is all thanks to Shio. Because at that time Shio held my hand, Because Shio showed me the way, I came to understand the meaning of happiness that I had never felt in my life. I always didn’t realize That the one who taught me what love is Was also Shio. Shio, after you are reincarnated, confess to me again. Sorry. Thank you.  This is my $\texttt {Happy Sugar Life}$

Satou and Shio give you a 2D plane. For two points $(x_1,y_1),(x_2,y_2)$ on the plane, we say they form a dominance pair (denoted as $(x_1,y_1)\le (x_2,y_2)$) if and only if $x_1\le x_2,\;y_1\le y_2$. Initially, there are $n$ distinct points $\{(x_i,y_i)\}_{i=1}^n$ on the plane. You need to answer $m$ queries. Each query gives two points $(x,y),(x',y')$ and asks how many ordered pairs $(i,j)$ satisfy $(x,y)\le (x_i,y_i)\le (x_j,y_j)\le (x',y')$ and $i \neq j$.

The first line contains two integers $n,m$. The second line contains $n$ integers. The $i$-th integer $p_i$ indicates that the $i$-th initially given point on the plane is $(i,p_i)$. It is guaranteed that $p_i$ is a permutation of $1$ to $n$. Then there are $m$ lines. Each line contains four integers separated by spaces, $x,x',y,y'$, representing one query. It is guaranteed that $(x,y)\le (x',y')$.

Output $m$ lines. The $i$-th line contains one integer, the answer to the $i$-th query.

Idea: ccz181078 & nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: nzhtl1477 & ccz181078. For $100\%$ of the data, $1 \le n \le 10^5$, $1 \le m \le 2 \times 10^5$. #### Sample Explanation For the first query, the points $(x_i,y_i)$ that satisfy $(x,y)\le (x_i,y_i)\le (x',y')$ are $(4,6),(6,4),(7,5),(8,3)$. The dominance pair is $(6,4),(7,5)$, and the corresponding ordered pair is $(6,7)$. For the second query, the points $(x_i,y_i)$ that satisfy $(x,y)\le (x_i,y_i)\le (x',y')$ are $(2,8),(3,7),(4,6),(5,2),(6,4),(7,5),(8,3),(9,1)$. The dominance pairs are $(5,2),(6,4)$, $(6,4),(7,5)$, $(5,2),(7,5)$, and $(5,2),(8,3)$, and the corresponding ordered pairs are $(5,6),(6,7),(5,7),(5,8)$. For the third query, the points $(x_i,y_i)$ that satisfy $(x,y)\le (x_i,y_i)\le (x',y')$ are $(5,2),(6,4),(8,3)$. The dominance pairs are $(5,2),(6,4)$ and $(5,2),(8,3)$, and the corresponding ordered pairs are $(5,6),(5,8)$. For the fourth query, the points $(x_i,y_i)$ that satisfy $(x,y)\le (x_i,y_i)\le (x',y')$ are $(4,6),(5,2),(6,4),(7,5),(8,3)$. The dominance pairs are $(5,2),(6,4)$, $(6,4),(7,5)$, $(5,2),(7,5)$, and $(5,2),(8,3)$, and the corresponding ordered pairs are $(5,6),(6,7),(5,7),(5,8)$. For the fifth query, the points $(x_i,y_i)$ that satisfy $(x,y)\le (x_i,y_i)\le (x',y')$ are $(4,6),(5,2),(6,4),(7,5),(8,3)$. The dominance pairs are $(5,2),(6,4)$, $(6,4),(7,5)$, $(5,2),(7,5)$, and $(5,2),(8,3)$, and the corresponding ordered pairs are $(5,6),(6,7),(5,7),(5,8)$. For the sixth query, the points $(x_i,y_i)$ that satisfy $(x,y)\le (x_i,y_i)\le (x',y')$ are $(1,9),(2,8),(3,7),(4,6),(5,2),(6,4),(7,5),(8,3),(9,1)$. The dominance pairs are $(5,2),(6,4)$, $(6,4),(7,5)$, $(5,2),(7,5)$, and $(5,2),(8,3)$, and the corresponding ordered pairs are $(5,6),(6,7),(5,7),(5,8)$. For the seventh query, the points $(x_i,y_i)$ that satisfy $(x,y)\le (x_i,y_i)\le (x',y')$ are $(3,7)$, and there are no dominance pairs. For the eighth query, there are no points $(x_i,y_i)$ satisfying $(x,y)\le (x_i,y_i)\le (x',y')$, and there are no dominance pairs. For the ninth query, there are no points $(x_i,y_i)$ satisfying $(x,y)\le (x_i,y_i)\le (x',y')$, and there are no dominance pairs. # Input Format # Output Format # Hint Translated by ChatGPT 5