[Cnoi2019] 数字游戏

咕咕咕~

给定一个长度为 $n$ 的一个 $1$~$n$ 的排列 $A_{1 - n}$。 给定 $q$ 个询问四元组 $( l, r, x, y )$ : 表示询问 有多少个二元组 $( u, v )$ 满足 : - $ [u, v] \neq \varnothing$ - $ [u, v] \subseteq [l, r] $ - $ \min\limits_{i \in [u, v]} \{ A_i \} \ge x$ - $ \max\limits_{i \in [u, v]} \{ A_i \} \le y$

第一行，两个整数 $n$, $q$. 第二行 $n$ 个整数，表示 $A$. 以下 $q$ 行，每行一个四元组询问.

$q$ 行，每一行表示一个询问的答案.

4 1
1 2 3 4
1 4 2 4

6

Subtask1( 34pts ) : $n, q \le 3*10^4$ Subtask2( 66pts ) : $n, q \le 2*10^5$