P5386 [Cnoi2019] Number Game

Given a permutation $\pi$ of $1 \sim n$, and $q$ queries. Each query contains an integer quadruple $( l, r, x, y )$, asking how many integer pairs $( u, v )$ satisfy: - $l \le u \le v \le r$; - and for all $\forall u \le i \le v$, we have $x \le \pi_i \le y$.

The first line contains two integers $n$ and $q$. The second line contains $n$ integers, representing $\pi$. In the next $q$ lines, each line contains one query quadruple.

Output $q$ lines, where each line is the answer to one query.

Subtask 1 ($34$ points): $1 \le n, q \le 3 \times 10^4$. Subtask 2 ($66$ points): $1 \le n, q \le 2 \times 10^5$. Translated by ChatGPT 5