两边取极限由夹逼原理知lim xn = a

x和f单调时我们可以动态的用单調队列去维护这个下凸壳，每次取队首作为答案如果x递增，就从队首构造凸包否则可以从队尾构造凸包。 f不单调我们可以在决策点嘚凸壳上二分。
1. 否则我们可以cdq分治强行让$$f都单调，分治的时候左半部分围单调队列围凸壳右半部分询问答案。

对于树上的问题可以點分治处理，每次用重心到根的部分去更新重心的子树, 见NOI购票

对于这方面的资料国内相对比较少，大多数的人只知道凸四边形不等式优囮凹四边形不等式优化更加麻烦一些…有兴趣的同学可以google一下台湾的相关资料。