题目描述
译自 ROI 2025 Day2 T4. Жизнь программистов
一部关于程序员生活的全新电视剧即将在天狼星电视台播出!这部剧共有 n 集,编号从 1 到 n。电视台计划在 k 天内按顺序从第一集到最后一集播放,每天播出一个或多个连续剧集的放送块。每集都恰好播放一次。
经过试播反馈,市场团队为每集评定了吸引力指数:第 i 集的指数为 ai,范围从 1 到 n,其中 1 表示最吸引人的剧集,n 表示最无聊的剧集。每集的指数互不相同,因此 [a1,a2,…,an] 构成一个从 1 到 n 的排列。
假设你已经决定好每天播放哪些剧集。每天的吸引力指数定义为当天播放的最无聊剧集的指数。换句话说,如果第 j 天播放从第 lj 集到第 rj 集,那么当天的指数 bj 是 [alj,alj+1,…,arj] 中的最大值。
为了让这部剧大获成功,吸引观众持续追剧,你需要在所有可能的 k 天放送方案中,找到一个让每天的吸引力指数序列 [b1,b2,…,bk] 字典序最小的方案。具体来说,先尽量让第一天的 b1 最小;在 b1 最优的情况下,尽量让第二天的 b2 最小;依此类推。
你需要回答 q 个询问,每个询问由两个数字 k 和 i 组成。你要输出在 k 天放送的最佳方案中,第 i 天的吸引力指数 bi。
输入格式
第一行包含两个整数 n 和 q (1≤n,q≤300000),分别表示剧集总数和询问数量。
第二行包含 n 个整数 a1,a2,…,an (1≤ai≤n),表示每集的吸引力指数。保证 [a1,a2,…,an] 是从 1 到 n 的一个排列。
接下来的 q 行,每行包含两个整数 k 和 i (1≤i≤k≤n),表示一个询问的放送天数和需要查询的天数。
输出格式
输出 q 行,按输入顺序回答每个询问,输出最佳方案中第 i 天的吸引力指数 bi。
7 4
6 4 2 3 1 7 5
7 4
1 1
4 2
5 3
3
7
1
3
3 1
2 3 1
2 2
3
提示
样例解释 1
- 当 k=7 时,只有一种放送方式:每天播出一集。每日剧集的吸引力指数为 [6],[4],[2],[3],[1],[7],[5],因此 b=[6,4,2,3,1,7,5]。对于询问 k=7 和 i=4,答案为 b4=3。
- 当 k=1 时,只有一种放送方式:第一天播出所有剧集。每日剧集的吸引力指数为 [6,4,2,3,1,7,5],因此 b=[7]。对于询问 k=1 和 i=1,答案为 b1=7。
- 当 k=4 时,最优方案是第一天播出 4 集,之后三天每天播出 1 集。每日剧集的吸引力指数为 [6,4,2,3],[1],[7],[5],因此 b=[6,1,7,5]。对于询问 k=4 和 i=2,答案为 b2=1。
- 当 k=5 时,最优方案是第一天和最后一天各播出 2 集,其余三天每天播出 1 集。每日剧集的吸引力指数为 [6,4],[2],[3],[1],[7,5],因此 b=[6,2,3,1,7]。对于询问 k=5 和 i=3,答案为 b3=3。
详细子任务附加限制及分值如下表所示。其中子任务 0 是样例。
子任务 |
分值 |
附加限制 |
0 |
样例 |
1 |
5 |
n≤20 |
2 |
8 |
k=2 |
3 |
k=3 |
4 |
排列形如 1,n,2,n−1,… |
5 |
8 |
n≤200 |
6 |
7 |
n≤3000 |
7 |
5 |
所有询问的 k 值总数不超过 10 |
8 |
i≤3 |
9 |
10 |
满足 ai<ai+1 的 i 数量不超过 20 |
10 |
8 |
满足 ai>ai+1 的 i 数量不超过 20 |
11 |
12 |
排列为随机生成 |
12 |
10 |
n≤105 |
13 |
无附加限制 |