#P12508. 「ROI 2025 Day2」程序员的日常

「ROI 2025 Day2」程序员的日常

题目描述

译自 ROI 2025 Day2 T4. Жизнь программистов

一部关于程序员生活的全新电视剧即将在天狼星电视台播出!这部剧共有 nn 集,编号从 11nn。电视台计划在 kk 天内按顺序从第一集到最后一集播放,每天播出一个或多个连续剧集的放送块。每集都恰好播放一次。

经过试播反馈,市场团队为每集评定了吸引力指数:第 ii 集的指数为 aia_i,范围从 11nn,其中 11 表示最吸引人的剧集,nn 表示最无聊的剧集。每集的指数互不相同,因此 [a1,a2,,an][a_1, a_2, \ldots, a_n] 构成一个从 11nn 的排列。

假设你已经决定好每天播放哪些剧集。每天的吸引力指数定义为当天播放的最无聊剧集的指数。换句话说,如果第 jj 天播放从第 ljl_j 集到第 rjr_j 集,那么当天的指数 bjb_j[alj,alj+1,,arj][a_{l_j}, a_{l_j+1}, \ldots, a_{r_j}] 中的最大值。

为了让这部剧大获成功,吸引观众持续追剧,你需要在所有可能的 kk 天放送方案中,找到一个让每天的吸引力指数序列 [b1,b2,,bk][b_1, b_2, \ldots, b_k] 字典序最小的方案。具体来说,先尽量让第一天的 b1b_1 最小;在 b1b_1 最优的情况下,尽量让第二天的 b2b_2 最小;依此类推。

你需要回答 qq 个询问,每个询问由两个数字 kkii 组成。你要输出在 kk 天放送的最佳方案中,第 ii 天的吸引力指数 bib_i

输入格式

第一行包含两个整数 nnqq (1n,q300000)(1 \le n, q \le 300\,000),分别表示剧集总数和询问数量。

第二行包含 nn 个整数 a1,a2,,ana_1, a_2, \ldots, a_n (1ain)(1 \le a_i \le n),表示每集的吸引力指数。保证 [a1,a2,,an][a_1, a_2, \ldots, a_n] 是从 11nn 的一个排列。

接下来的 qq 行,每行包含两个整数 kkii (1ikn)(1 \le i \le k \le n),表示一个询问的放送天数和需要查询的天数。

输出格式

输出 qq 行,按输入顺序回答每个询问,输出最佳方案中第 ii 天的吸引力指数 bib_i

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=7k = 7 时,只有一种放送方式:每天播出一集。每日剧集的吸引力指数为 [6],[4],[2],[3],[1],[7],[5][6], [4], [2], [3], [1], [7], [5],因此 b=[6,4,2,3,1,7,5]b = [6, 4, 2, 3, 1, 7, 5]。对于询问 k=7k = 7i=4i = 4,答案为 b4=3b_4 = 3
  • k=1k = 1 时,只有一种放送方式:第一天播出所有剧集。每日剧集的吸引力指数为 [6,4,2,3,1,7,5][6, 4, 2, 3, 1, 7, 5],因此 b=[7]b = [7]。对于询问 k=1k = 1i=1i = 1,答案为 b1=7b_1 = 7
  • k=4k = 4 时,最优方案是第一天播出 44 集,之后三天每天播出 11 集。每日剧集的吸引力指数为 [6,4,2,3],[1],[7],[5][6, 4, 2, 3], [1], [7], [5],因此 b=[6,1,7,5]b = [6, 1, 7, 5]。对于询问 k=4k = 4i=2i = 2,答案为 b2=1b_2 = 1
  • k=5k = 5 时,最优方案是第一天和最后一天各播出 22 集,其余三天每天播出 11 集。每日剧集的吸引力指数为 [6,4],[2],[3],[1],[7,5][6, 4], [2], [3], [1], [7, 5],因此 b=[6,2,3,1,7]b = [6, 2, 3, 1, 7]。对于询问 k=5k = 5i=3i = 3,答案为 b3=3b_3 = 3

详细子任务附加限制及分值如下表所示。其中子任务 00 是样例。

子任务 分值 附加限制
00 样例
11 55 n20n \le 20
22 88 k=2k = 2
33 k=3k = 3
44 排列形如 1,n,2,n1,1, n, 2, n-1, \ldots
55 88 n200n \le 200
66 77 n3000n \le 3000
77 55 所有询问的 kk 值总数不超过 1010
88 i3i \le 3
99 1010 满足 ai<ai+1a_i < a_{i+1}ii 数量不超过 2020
1010 88 满足 ai>ai+1a_i > a_{i+1}ii 数量不超过 2020
1111 1212 排列为随机生成
1212 1010 n105n \le 10^5
1313 无附加限制