[国家集训队] Tree I

借助这道题目把wqs二分讲明白

考虑如下一个问题：

现在一共有若干个物品，物品被分成两组，现在从中选出若干个物品，但是题目会给出某种限制（也就是在这种限制条件下，物品的选择不是随意的，所有选择集合中，只有一些集合符合题目给出的限制，这样的集合才可以被选择），这种限制只跟物品本身有关而跟其权值无关（i.e. 对一个相同的物品选择集合，其中的物品权值无论如何变化，这个集合的合法性都不改变），而且必须从第一类物品中选出\(p\)个，问如何选择最优

我们设\(g(x)\)表示从第一类物品选出\(x\)个且满足题目限制的最优答案，如果说\(g(x)\)是一个凹凸函数，那么就可以利用wqs二分

比如\(g\)长成下面这个样子

那么如果题目给出的\(p=9\)，那么答案就是\(g(9)=5\)

显然我们是不能求出\(g(x)\)的（否则可以直接输出了），我们要想办法把\(g\)搞出来

假设现在有一条直线，斜率为\(k\)，令其通过函数上的每一个点（注意函数是离散的），则有

通过\((x_0,g(x_0))\)的直线方程就是\(y-g(x_0)=k(x-x_0)\)

我们给第一类物品的权值都减去\(k\)，然后不管\(p\)了，在题目的限制条件下跑出来一个值\(res\)，那么\(res\)是什么？

\(res\)其实就是上面画的所有直线的截距的最大值

为什么？我们将直线写成\(y-kx=g(x_0)-kx_0\)，注意现在\(k\)是已知量。在最初的情况下，假设我们对每个\(x_0\)都跑出来了一个最优解\(g(x_0)\)，而在减\(k\)的情况下，每个\(x_0\)的最优解就是\(g(x_0)-kx_0\)（因为权值的变化不会影响限制）。由于现在我们不管\(p\)了，只在题目的限制条件下跑出来了一个最优解，那么就是我们遍历了所有\(x_0\)取最优解的最优解，也就是\(max(g(x_0)-kx_0)\)