题解：P10159 [DTCPC 2024] The last permutation

· · 题解

官方题解

考虑从序列从前向后确定每个值，对 [1,i-1] 二分 rank 可以得到 i，代价为 \sum \frac{1}{i}\log i，代价大约 34。

考虑值域从大到小确定每个值，当求出前 x 大时，很容易设计一个比较器，使得在一次询问内求出区间 [l,r] 内是否包含第 x+1 大。

一个有趣的发现：将序列分两份，我们可以用一次询问来确定 x 在序列的左侧还是右侧，之后每次二分的时候我们都保证了询问区间长度 >\frac{n}{2}。

这样可以容易做到 n\times \frac{2}{n}\times (\log n+1)。大约是 22 次。

考虑结合两个做法，把序列分两段，用 1 的代价确定两块的构成，然后运用做法一，可以做到 \sum \frac{1}{\max\{i,n-i\}}\log i，大约是 14 次。

还能不能再给力一点！注意到 \log i 实现的精细一点可以做到 \log \min\{i,n-i+1\}，这样理论分析就可以做到 <11.8 次。

经过构造可以把标算卡到基本满。