AC. 梦想

frank_c1

[APIO 2016] Gap

发布于2017年04月15日 | 暂无评论 | 334阅读 | 未分类

题意简述

交互题。

交互库有一个数组a,长度为n。数组元素单调递增,均是整数,在[0, 10 ^ {18}]范围内。

你可以询问若干次,每次询问一个区间[s, t],返回所有值在[s, t]中的最小值和最大值。

a_{i+1} - a_i的最大值。有两类数据。

子任务1:每次询问代价为1。询问代价总和不超过\lfloor \frac{n+1} {2} \rfloor

子任务2:每次询问代价为[s, t]中元素个数+1,询问代价总和不超过3n

2 \le n \le 10 ^ 5

算法讨论

对于子任务1,由于单次询问代价都是1,那么考虑暴力,每次把剩下元素的最小最大值问出来去掉。恰好\lfloor \frac{n+1} {2} \rfloor次。

对于子任务2,由于单次询问涉及到元素个数,那么显然每个元素只能被访问O(1)次。不妨考虑分块。怎么设置块的大小呢?考虑题目条件,由于是要求a_{i+1} - a_i的最大值,所以由鸽巢原理知道答案不少于\lfloor \frac{a_{\max} - a_{\min}} {n} \rfloor,于是我们可以把这个值作为块大小,询问每个块中最小最大值,用相邻块的相邻端点来更新答案。一开始我们需要问出a_{\max},a_{\min},代价n+1。后续总共n次询问,贡献为n。除去右端点,其他每个元素在后续询问中恰好被访问1次,代价n-1,于是恰好3n次,可以通过。