记某类决策单调性 trick 最后更新于 2025-05-01 16:29:16

发现自己是真不会这玩意，开个坑记一记遇到过的 trick。 ## 对于允许离线问题的分治做法 [PR#4 赌徒](https://pjudge.ac/contest/942/problem/21650) 不叙述单调栈维护凸包的做法。 考虑枚举 $i$ 那么会会形成一个关于 $i$ 的函数，显然这有决策单调性，证明不再叙述。 场上想出来了一个假掉的双指针做法，对于每个 $i$ 去维护一个 $j$，每次单调前移。 可以取得 85pts 的好成绩，假掉的原因是因为尽管你最优决策点 $j'$ 是单调移动的，但是 $[j',j]$ 这段函数图像并不是单调的，所以可能出现动不过去的情况。 这时候可以考虑分治。 我们对于 $i\in[l,r]$，算出 $\left\lfloor\frac{l+r}{2}\right\rfloor$ 在 $j\in[L,R]$ 的最优决策点 $j'$，根据决策单调性，你 $[l,\left\lfloor\frac{l+r}{2}\right\rfloor-1]$ 的最优决策点一定在 $[j',R]$，$[\left\lfloor\frac{l+r}{2}\right\rfloor+1,r]$ 的最优决策点一定在 $[L,j']$，分治做下去就行了，复杂度 $O(n\log n)$。 局限性比较大，对于半/全在线问题无法使用。 ## 关于半在线的单调队列 [诗人小 G](https://www.luogu.com.cn/problem/P1912) 哎不是我咋现在才会这玩意。 你考虑一个长成 $f_i=f_j+W$ 的 DP 式子，其中 $W$ 是个凸函数还有决策单调性，那么你对于每个 $j$ 你给他塞单调队列里，关键字是和相邻位置 $k$ 的决策等价点（即在等价点左侧决策点是 $j$，右侧是 $k$），等价点直接二分求即可。 然后实现不精细的话常熟很大（详情见花花的手动加强版 P9266）。