#P12646. [KOI 2024 Round 1] 升序
[KOI 2024 Round 1] 升序
题目背景
试题来源:https://koi.or.kr/archives/。中文翻译做了少量本土化修改。
按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。
题目描述
给定一个长度为 的正整数序列 ,我们希望将这个序列变为升序。一个序列 是升序的,当且仅当对所有 ()满足 。
为了将序列 变为升序,可以对其应用如下操作任意次数(包括 次):
- 对于某个 (),将 乘以 。
我们将通过最少的操作次数将 变为升序时所需的操作次数记为 。
现在,给定一个长度为 的正整数序列 ,以及 个查询。每个查询给出两个整数 和 ,满足 。查询的目标是计算 ,即将从 中截取的子序列升序所需的最小操作次数。
请计算并输出每个查询的答案。
输入格式
第一行输入两个整数 和 ,用空格分隔。
第二行输入 个整数 ,用空格分隔。
接下来的 行,每行输入两个整数 和 ,表示一次查询。
输出格式
输出 行,第 行输出第 个查询的答案。
10 5
5 2 7 3 2 9 6 3 3 5
3 9
1 10
1 8
2 4
8 9
14
27
19
2
0
10 5
2 8 4 9 10 8 5 3 7 7
2 8
1 10
3 3
1 3
8 10
7
11
0
1
0
提示
约束条件
- 所有输入均为整数。
- 对所有查询满足
子问题
1.(5 分)
2.(7 分)
3.(28 分)所有查询满足
4.(10 分)对所有 满足
5.(5 分)对所有 满足
6.(10 分)对所有 存在非负整数 使得
7.(35 分)无额外限制条件
翻译由 ChatGPT-4o 完成