#P12554. [集训队互测 2024day7]不是这一道据数构结题

    ID: 11717 传统题 2000ms 1024MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600数据结构树状数组ST表堆栈排序队列

[集训队互测 2024day7]不是这一道据数构结题

给定一个长度为 nn 的序列 aa,qq 次询问,每次询问一个区间 [l,r][l,r] 的权值 f(al∼r)f(a_{l\sim r})。

f(A)f(A) 定义为:执行 mm 轮操作,非空的轮数。

具体的,令 AA 数组长度为 mm,则执行 mm 轮操作。

第 ii 轮从 ii 开始,依次检查 AiA_i 与 A_i+1∼AmA\_{i+1}\sim A_{m} 的大小关系,设当前检查 AiA_i 与 AtA_t 的大小关系,若 Ai<AtA_i<A_t 则交换 AiA_i 与 AtA_t,若第 ii 轮进行了至少一次交换,称这一轮非空。

具体的,以 f([1,4,2,3])f([1,4,2,3]) 为例,每一轮操作之后,数组分别为 [4,1,2,3],[4,3,1,2],[4,3,2,1],[4,3,2,1][4,1,2,3],[4,3,1,2],[4,3,2,1],[4,3,2,1],前 3 轮是非空的,所以 f([1,4,2,3])=3f([1,4,2,3])=3。

注意,f 函数对 原数组 aa 不造成任何实质上的影响,仅用于计算权值。

输入格式

第一行输入两个整数表示 n,q。 接下来一行输入 n 个整数表示 a 数组。 接下来输入 q 行,每行两个整数表示每次询问的区间。

输出格式

输出共 q 行,每行一个整数表示该组询问的答案。

样例输入 1

5 5
2 2 1 3 3
1 2
1 5 
2 4
2 5
1 4

样例输出 1

0
4
2
3
2

样例输入 2

10 10
4 10 4 8 2 3 3 10 6 8 
3 4
4 4
3 5
8 9
2 5
10 10
1 2
1 5
1 4
7 8

样例输出 2

1
0
1
0
1
0
1
2
2
1

样例 3

见 下发文件 。

数据范围与提示

对于所有的数据,满足 1≤n,q≤106,1≤ai≤n1 \le n, q \le 10^6, 1 \le a_i \le n。

测试点编号 n,qn,q 是否 aa 形如排列
1∼11\sim 1 ≤100\le 100 是
2∼22\sim 2 否
3∼53\sim 5 ≤3000\le 3000 是
6∼86\sim 8 否
9∼109\sim 10 ≤10000\le 10000 是
11∼1211\sim 12 否
13∼1313\sim 13 ≤200000\le 200000 是
14∼1614\sim 16 否
17∼1717\sim 17 ≤1000000\le 1000000 是
18∼2018\sim 20 否