关于决策点单调右移的小杂谈

决策点单调右移

如果是简单的决策点单调右移，分治即可搞定。

为什么是对原数组二分？难道决策点区间每次不减少二分之一也是对的。

可以发现每一层是 $O(n)$ ，而对原数组二分则是限制了层数是 $O(\log)$ 的。

因此时间复杂度是 $O(n\log{n})$ 。

非常妙的分治做法啊，限制层数以达到 $\log$ 复杂度。

如果在此基础上，有更强的单调性，则可以直接双指针。

即如果 x<y<z 且 ax<az ，那么有 ax<ay<az ，则可以直接双指针转移。

时间复杂度可以优化到：$O(n)$ 。

做题做到一道很有趣的决策点单调右移。

十分显然的决策点单调左移，但是乍一看并不满足单调性，因此我当时采用了分治做法，事实上也确实能过，但是这道题目不止于此。

如果把 $(a,b)$ 看成一个点，那么query函数就可以看成过这个点的一条斜线在 y 轴的截距，求最大截距，显然，答案只可能出在凸包上。

而且不难发现答案在凸包上具有单调性，于是可以用双指针做到 O(n) 。（有亿点像斜率优化）

不过可惜的是排序的 log 去不掉。

感觉是十分 NB 的决策点单调右移题目。

看完这道题目的题解，我开始思考，如果我不会分治做决策点单调右移题目，我是不是有机会想出这个双指针做法？

就像一些古文明没发展出铜，但是打制石器却能到今天的人都可望而不可即的境界。

后面，我想明白了，强不是限制自己的科技树从而做到某些方面登峰造极，而是在做到知识面开阔的情况还能灵活应用，这才是真正的高难度，真正的强者。

当然，这也是为什么某些人（包括我自己）知识面变得更加开阔的时候反而变得更弱的原因，所以只能说学知识是把双刃剑，能熟练掌握才是真正的神仙啊。