#P17770. 数字游戏

数字游戏

P5386 [Cnoi2019]

题目描述

给定一个 1∼n1\sim n 的排列 π\pi,以及 qq 个询问,每个询问包含一个整数四元组 (l,r,x,y)( l, r, x, y ),表示查询有多少个整数二元组 (u,v)( u, v ) 满足:

  • l≤u≤v≤rl\le u\le v\le r;
  • 且对于任意 u≤i≤v u\le i\le v,有 x≤πi≤yx\le\pi_i\le y。

输入格式

第一行,两个整数 nn,qq。

第二行 nn 个整数,表示 π\pi。

以下 qq 行,每行一个四元组询问。

输出格式

qq 行,每一行表示一个询问的答案。

输入输出样例 #1

输入 #1

4 1
1 2 3 4
1 4 2 4

输出 #1

6

说明/提示

子任务 1(3434 points):1≤n,q≤3×1041\le n, q \le 3\times10^4。

子任务 2(6666 points):1≤n,q≤2×1051\le n, q \le 2\times10^5。