Background

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}$

Problem Description

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$.

Input Format

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 Format

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

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
4
2
4
4
4
0
0
0

Hint

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