#PQJ1421x7771. QOJ 1421_7771

    ID: 2602 传统题 2000ms 1024MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2023-2024 集训队互测模拟

QOJ 1421_7771

标题: 不是这一道据数构结题 - Problem - QOJ.ac

#7771. 不是这一道据数构结题

Statistics

The problem was used in the following contests:

给定一个长度为 n 的序列 a,q 次询问,每次询问一个区间 [l,r] 的权值 f(al∼r)。

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

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

第 i 轮从 i 开始,依次检查 Ai 与 A_i+1∼Am 的大小关系,设当前检查 Ai 与 At 的大小关系,若 Ai<At 则交换 Ai 与 At,若第 i 轮进行了至少一次交换,称这一轮非空。

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

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

输入格式

第一行输入两个整数表示 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≤n。

测试点编号n,q是否 a 形如排列1∼1≤100是2∼2≤100否3∼5≤3000是6∼8≤3000否9∼10≤10000是11∼12≤10000否13∼13≤200000是14∼16≤200000否17∼17≤1000000是18∼20≤1000000否