题解：P11677 [USACO25JAN] Shock Wave P

下文默认 1-index。

注意到对于 $1<x<n$ 的位置，至多进行一次操作。证明就是考虑若选了两个非 $1,n$ 位置 $x\le y$ 进行操作，会发现不如操作 $x-1,y+1$ 优。令最终 $1$ 操作了 $a$ 次，$n$ 操作了 $b$ 次。我们先二分出只用 $1,n$ 操作的答案，随后 check 下答案能否通过非 $1,n$ 操作取到 $ans-1$ 即可。

二分出仅用 $1,n$ 操作的答案是容易的。令 $a+b=mid$，分别讨论 $2i\le n,2i=n+1,2i>n+1$ 可以得到 $a,b$ 的下界，判断两个下界加起来是否小于等于 $mid$ 即可。注意这里要特判分母为 $0$ 的情况。下文令这个二分出来的答案为 $ans$。

现在我们加上中间的操作 $m$，重新写一下上面 check 的式子，会多出来一项 $-|m-i|$。暴力做是平方老哥级别的，无法通过。注意到下界的分母是 $n-2i+1/2i-n-1$ 这启示我们考虑本质不同的下界取值，注意到其只有 $O(n\log n)$ 种，因此我们用两个优先队列（里面放 $m,i$ 与当前下界）维护当前最严格的下界限制，每次暴力更新下界即可，复杂度 $O(n\log n\log V)$。注意这里由于分母的正负性，需要从左至右以及从右至左跑两遍。

说下实现细节。