题解「夜雀 cooking」

· · 题解

这里是八云蓝的官方题解~

\textbf{Subtask1}

直接二分即可，蓝不再赘述。

\textbf{Subtask2} $40\%$ 分数的解法：首先考虑“随机数据”带来的性质。对于一个长度为 $n$ 的序列，若从其中均匀的选出 $x$ 个位置作为紫色位置，那么每 $\frac{n}{m}$ 个位置中期望恰好有一个紫色位置。考虑将序列分成 $m$ 个大小为 $\frac{n}{m}$ 的块，期望下，每个块都恰好有一个紫色位置。注意到数据是基本均匀随机，所以可能有一定数量的块不满足该性质，直接用 $20pts$ 的解法暴力做即可。判断一个块内是否有紫色位置是很简单的，所以问题转化为判断块内是否存在切仅存在一个紫色位置，以及这个位置是什么。如果判断出了是否仅存在一个紫色位置的话，由于给出的等差数列公差大于等于 $1$，所以每个数互不相同，那么判断紫色位置是什么也就很简单啦。 - 如何判断“块内是否仅存在一个紫色位置”：对于一个块，块内数显然有从左往右单调递增，那么设这个块为区间 $[l,r]$，由于每个数都是正数，如果有 $a_l+a_{l+1}>a_r$，那么对于任意一个选出 $>1$ 个紫色点的情况，其紫色点的权值（也就是 $a$ 值）和一定大于任意一种选出恰好 $1$ 个紫色点的情况。所以显然的，对于满足 $a_l+a_{l+1}>a_r$ 的块，可以判断“块内是否仅存在一个紫色位置”。我们之后称满足这一条件的块或区间为有趣块或者有趣区间。 - 有趣块的数量：是 $m-1$。考虑下述的证明方法：对于序列 $a$ 有 $a_i=(i-1)k+s$。第一块不一定是有趣块，直接考虑第二块是否为有趣块。记 $\frac{n}{m}=L$，那么第二块的区间即为 $[L+1,2L]$。带入上面的不等式可得 $a_{L+1}+a_{L+2}>a_{2L}$，带入 $a_i=(i-1)k+s$ 得 $(2L+3)k+2s>2Lk+s$，由于 $k,s\geq1$，所以第二个块一定是有趣块。易证第二个块是有趣块，之后的块就一定是有趣块。于是有趣块数即为 $m-1$。 综上，我们可以达到一个比较优的询问次数。这足以让我们拿到 sub2 的 $40%$ 的分数。 $100pts$ 的做法：虽然上述做法看起来很优，但是多次调用 gen 可以发现，数据仅是比较均匀，它并没有我们想象中一样均匀，在很多时候，一个块内的数数量会大于 $1$。好消息是，一个块内的数的期望很小，也就是说，一个块内不会有很多数。并且，这些块内的数的分布仍是比较均匀的。第一个块不是有趣块，于是这个块我们暴力二分。对于其他的块，蓝有更为优雅的解决方案。 - 如何优雅的处理有趣块（本部分轻微卡常）：考虑一个类似于线段树二分的做法，每次询问一个区间 $[l,r]$，如果这个区间内有紫色位置的话就取 $mid$，继续询问区间 $[l,mid]$，否则令上一次询问的区间为 $[l',r']$，询问 $[r+1,r']$。注意到在这样二分的时候，如果某一块内注意到，如果对于一个块 $[l,r]$，你询问了 $[l,x]$，那么你就可以通过相减的方式得到 $[x+1,r]$ 内的紫色位置的权值和。并且有一个简单优化——如果当前询问的区间有且仅有一个紫色位置，那么可以直接求出这个位置（易证一个有趣块的子区间是有趣区间）。 综上，我们可以在 $200T$ 的限制下稳定的通过此题。 update：赛时有人不分块就过题了，而且比起分块优化显著，所以分块其实并没有必要的说。但是对于第一块的特判是必须的（赛时没有卡住，向大家谢罪）。