主要是因为网上的 wqs 二分文章有点太难懂了（起码对于我），连带着斜率优化和决策单调性一起讲了，顺便梳理一下这几天的学习。
凸包/斜率优化。
> 定义凸包：平面上一些点，能将这些点包围起来的最小凸多边形称为凸包。
假设你会凸包。不会的也别急，很好理解的（真的）。
“凸”其实就是间距尽量小的时候的差分数组单调。比如 y=x2+3x−2y=x^2+3x-2y=x2+3x−2 就是凸函数（上凸），y=−x2+3x−2y=-x^2+3x-2y=−x2+3x−2 也是凸函数（下凸），y=1x(x>0)y=\dfrac{1}{x}(x>0)y=x1 (x>0) 不是，y=1x(x<0)y=\dfrac{1}{x}(x<0)y=x1 (x<0) 是。
不妨变化标准形式（AAA 和 BBB 和 DDD 都是来自 iii 的系数，CCC 可以理解为转移方程的 fff，xjx_jxj 和 yjy_jyj 都可以看作和 jjj 相关的数，可以是任意数，也可以是和 CCC 相关的）：
Ci=minj=l(i)r(i)(Aixj+Biyj+Di)=Di+Biminj=l(i)r(i)(AiBixj+yj)=Di+Biminj=l(i)r(i)(yj−(−AiBixj))C_i=\min\limits^{r(i)}_{j=l(i)}(A_ix_j+B_iy_j+D_i)=D_i+B_i\min\limits^{r(i)}_{j=l(i)}(\dfrac{A_i}{B_i}x_j+y_j)=D_i+B_i\min\limits^{r(i)}_{j=l(i)}(y_j-(-\dfrac{A_i}{B_i}x_j))Ci =j=l(i)minr(i) (Ai xj +Bi yj
+Di )=Di +Bi j=l(i)minr(i) (Bi Ai xj +yj )=Di +Bi j=l(i)minr(i) (yj −(−Bi Ai xj ))。
这玩意是不是像直线解析式？后面的 min\minmin 中就是直线的交点（也就是截距）（b=y−kxb=y-kxb=y−kx）。那么每个点可以转换为 (xj,yj)(x_j,y_j)(xj ,yj )，斜率就是 −AiBi-\dfrac{A_i}{B_i}−Bi Ai 。
由于凸包将所有点都给包起来了，所以最优决策点肯定是在这个凸包的边缘去到。我相信你们是会凸包的。
不同的场景对应不同的实现：
1. 用平衡树维护凸壳．那么寻找决策点的二分操作就转化为在平衡树上二分，插入决策点就转化为在平衡树上插入一个结点，并删除若干个被踢出凸壳的点．此方法思路简洁但实现繁琐（来自 OI-wiki）。此时你可以做任何问题（可以区间查询）。（我不会，见谅 /bq）
2. 使用 CDQ 分治（按时间分治）。先将分治的前半部分的 dp 算出来，再建立凸包，接着对于 [mid+1..r][mid+1..r][mid+1..r] 的，去二分截距切凸包。二分做法：以上凸壳为例，二分答案，以 kkk 为斜率经过 midmidmid 点的截距与 mid−1mid-1mid−1 的截距做差分，判断正负以来判断实在这个峰的哪里。
3. 如果 xxx 具有单调性，可以直接维护一个单调栈，然后做二分。二分同上。
4. 如果 xxx 和 kkk 都有单调性，那么可以维护单调栈，在 3 的基础上可以发现最优点是一直向右边移的，所以可以维护一个指针表示最优取值。
决策单调性只能做到 log\loglog，但是有的时候可以用特殊的 4 情况，可以做到线性，会在最终的大汇总例题见到。
可以先拿 P3195 玩具装箱 练练手（其实这个题的 kkk 和 xxx 已经是单调递增的了，可以用 4 写法写写做到线性，也可以用其他的练练手）。代码很简单吧。题解区自认为够了。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
wqs 二分。
它可以节约状态数。通常是将 f(i,j)f(i,j)f(i,j) 优化成 g(j)g(j)g(j) 的，同时复杂度也大大降低（通常是 O(nm)→O(nlogV)O(nm)\to O(n\log V)O(nm)→O(nlogV)，这里 iii 是 nnn 量，jjj 是 mmm 量）。但是可惜的是他的条件很苛刻。
举个例子：最大多区间和。
> 给你一个长度为 nnn 的序列 aaa，aaa 可正可负，你要选出恰好 mmm 个不相交和包含的区间（这里可以将“恰好”做到“至多”），使得这些区间的数的加和尽量大。（把 nnn 和 mmm 看作同阶）（这里由于还没讲决策单调性，将 O(nlognlogV)O(n \log n \log V)O(nlognlogV) 的做法先搁一搁，假设允许 O(n2logV)O(n^2\log V)O(n2logV) 通过）。
典型的做法：f(i,j)f(i,j)f(i,j) 表示前 iii 个数中选取 jjj 个数后，和的最大值。f(i,j)=max(f(i−1,j),maxk(f(k,j−1)+w(k,i)))f(i,j)=\max(f(i-1,j),\max_{k}(f(k,j-1)+w(k,i)))f(i,j)=max(f(i−1,j),maxk (f(k,j−1)+w(k,i)))。w(k,i)=si−skw(k,i)=s_i-s_kw(k,i)=si −sk ，sss 是前缀和。
定义 g(i)g(i)g(i) 表示全局选 iii 个区间的最大区间和（g(j)=maxf(i,j)g(j)=\max f(i,j)g(j)=maxf(i,j)）。
ggg 具有凸性。用贪心的方法证明，你选少的区间自然有些大点吃不到，你选多的区间自然有些负数你不得不吃，选的刚刚好才有最大得分。当然 写暴力去暴力枚举看下是否凸，但是不要只找小数据手模，因为可能只是个特例。记住要大胆猜测，论证管他的。
把点 (i,g(i))(i,g(i))(i,g(i)) 放到坐标系上。
让我来偷一个图(https://www.luogu.com.cn/article/knpufhxe)\tiny\text{让我来偷一个图(https://www.luogu.com.cn/article/knpufhxe)} 让我来偷一个图(https://www.luogu.com.cn/article/knpufhxe)
为了方便说明，记 p(i,k)p(i,k)p(i,k) 表示过 iii 的斜率为 kkk 的直线，截距为 p(i,k)p(i,k)p(i,k)。
假设我们知道了经过点 mmm 的线的 kkk 和 p(i,k)p(i,k)p(i,k)（斜率和截距），显而易见可以求出 g(m)g(m)g(m)。由于 kkk 任意，不妨找到所有点中某个 kkk 时 p(i,k)p(i,k)p(i,k) 是最大的（这个为什么能做接下来说）。捋一下，这个时候我们就将问题转换成了这个：
> 找到一个截距 kkk，使得所有点中，p(m,k)p(m,k)p(m,k) 是最大的。
（例如，m=1 时候 k=1.5，m=2 时候 k=0.9）
让我再来偷一张图，网址同上\tiny\text{让我再来偷一张图，网址同上} 让我再来偷一张图，网址同上
由于凸性的定义，斜率单调，那么取到 ppp 极值的时候 kkk 也是单调的（例如上上个图，分别是 1.5，0.9，0.4，当然不止一个数）。那么我们就可以二分这个 kkk，直到他落到 mmm 点上！（就像上图一样）
好了，思想铺垫弄完了，咋求这个截距？？？
你将截距公式弄出来：bi=yi−kxi=g(i)−kib_i=y_i-kx_i=g(i)-kibi =yi −kxi =g(i)−ki。你会发现这个就相当于是你选 iii 个区间后要被惩罚掉 kikiki。也就是说每次选一个区间，你将受到 kkk 的惩罚。
你已经有 kkk 了，定义 h(i,j)h(i,j)h(i,j) 表示在前 iii 个数内，选 jjj 个区间，每选一个区间你将会受到 kkk 的惩罚，这样子的最大值。
显然：h(i,j)=max(h(i−1,j),−k+maxu(h(u,j−1)+w(u,i)))h(i,j)=\max(h(i-1,j),-k+\max_u (h(u,j-1)+w(u,i)))h(i,j)=max(h(i−1,j),−k+maxu (h(u,j−1)+w(u,i)))。
事实上，你只关心 maxh(n,j)\max h(n,j)maxh(n,j) 和取得最值的 jjj。同理可得每个 iii 只管 hhh 最大的 jjj（你贪心地想，你无论选 222 个区间还是 333 个区间，你多选，总是会被惩罚的，与原来不同，永不惩罚。若 222 比 333 还优，选 333 不如选 222，因为最终只考虑所有 jjj 的 hhh 最值）。
那么 hhh 的最后一维可以去掉（h(i)=max(h(i−1),−k+maxu(h(u)+w(u,i)))h(i)=\max(h(i-1),-k+\max_u(h(u)+w(u,i)))h(i)=max(h(i−1),−k+maxu (h(u)+w(u,i)))），多记录一个数，表示取得最大值的 jjj 是哪个 jjj（因为二分时候要用到）。
这样 h(n)h(n)h(n) 就是截距最大值了！jjj 你只需要像二分同款思路一直改变 kkk 来逼近直到 j=mj=mj=m。不具体来说，如果 j>mj>mj>m 咋样咋样，j≤mj\le mj≤m 咋样咋样。
最终二分内部 chk 需要 O(n2)O(n^2)O(n2)，总复杂度是 O(n2logV)O(n^2 \log V)O(n2logV)。配合上决策单调性，他会更强。
这里有个我的实现。来自 P1792 [国家集训队] 种树。
我这里简短的讲一讲，大部分可以自己推。由于是个环，可以做两次 dp，第一次考虑 1∼n−11 \sim n-11∼n−1，第二次考虑 2∼n2 \sim n2∼n，相当于 nnn 或 111 每种，自然保证相邻不会挂。dp 可以自己推推，凸性可以自己感性证明。
我的代码有输出方案数的，并且可以处理多点共线，可以参考下。
典型例题：https://www.luogu.com.cn/problem/P2619 （不用决策单调性的模板题）。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
决策单调性。
注意：此处的“决策”是名词“你从哪里转移过来的 dp”，而不是动词。
那么就可以理解为“你在哪里取得最值”的这个点是单调的。
所有决策单调性都依赖于四边形不等式。先讲四边形不等式。
> 定义 1：若 w(i,j)w(i,j)w(i,j) 满足四边形不等式，对于任意 a≤b≤c≤da \le b \le c \le da≤b≤c≤d，满足 w(a,c)+w(b,d)≤w(a,d)+w(b,c)w(a,c)+w(b,d) \le w(a,d)+w(b,c)w(a,c)+w(b,d)≤w(a,d)+w(b,c)。
> 定义 2：任意 a≤l≤r≤ba \le l \le r \le ba≤l≤r≤b，满足 w(l,r)≤w(a,b)w(l,r) \le w(a,b)w(l,r)≤w(a,b)，则称 www 满足区间包含单调性。
证明某个 www 满足四边形不等式：
1. 自己画数轴暴力拆（这个通常只解决 www 好表示的）（这个挺常用的，其他的都没见过）。
2. 若 w1(i,j)w_1(i,j)w1 (i,j) 和 w2(i,j)w_2(i,j)w2 (i,j) 都满足四边形不等式/恒等式/区间包含单调性，那么任意 c1,c2≥0c_1,c_2 \ge 0c1 ,c2 ≥0，c1w1+c2w2c_1w_1+c_2w_2c1 w1 +c2 w2 满足四边形不等式/恒等式/区间包含单调性。
3. 若存在函数 f(i)f(i)f(i) 和 g(i)g(i)g(i)（例如前缀和）使得 w(i,j)=f(i)−g(i)w(i,j)=f(i)-g(i)w(i,j)=f(i)−g(i)，那么 www 满足四边形恒等式。若 fff 和 ggg 单调增加、www 还满足区间包含单调性。
4. 若 h(x)h(x)h(x) 是个单调递增的凸函数，若 w(i,j)w(i,j)w(i,j) 满足四边形不等式并且对区间包含关系有单调性（可增可减），则 w1(i,j)=h(w(i,j))w_1(i,j)=h(w(i,j))w1 (i,j)=h(w(i,j)) 满足四边形不等式和区间包含单调性。
5. 若 h(x)h(x)h(x) 凸，w(i,j)w(i,j)w(i,j) 满足四边形恒等式和区间包含关系的单调性，那么 w1(i,j)=h(w(i,j))w_1(i,j)=h(w(i,j))w1 (i,j)=h(w(i,j)) 满足四边形不等式。
6. 最最最无敌的方法：如果你看某个 www 非常有四边形不等式，但是死活证明不出来，写暴力去暴力枚举几组看下决策点是否单调，但是不要只找小数据手模，因为可能只是个特例。记住要大胆猜测，论证管他的。
接下来我们引入最朴素形式。
> f(i)=min/maxjf(j)+w(j+1,i)f(i)=\min/\max_j f(j)+w(j+1,i)f(i)=min/maxj f(j)+w(j+1,i)。
记 opt(i)\text{opt}(i)opt(i) 表示 f(i)f(i)f(i) 取得极值时的 jjj（决策点）。
这个时候若 www 满足四边形不等式，opt\text{opt}opt 单调不下降（超级重要，核心结论）。证明看 OI-WIKI，只需要记住结论就可以了。
写法？这里介绍一种通用的简化 LARSCH 算法（来自 OI-WIKI，非常通用）。
考虑分治，divide(l,r)\text{divide}(l,r)divide(l,r) 表示求出 (l..r](l..r](l..r] 的所有 fff 值。
定义 mid=⌈l+r2⌉\text{mid}=\lceil\dfrac{l+r}{2}\rceilmid=⌈2l+r ⌉，假设这个时候 lll 和 rrr 的 fff 和 opt\text{opt}opt 都已经部分确定了，那么显然 optl≤optmid≤optr\text{opt}_l \le \text{opt}_{\text{mid}} \le \text{opt}_roptl ≤optmid ≤optr 。
那么你就可以枚举决策点（optl\text{opt}_loptl 和 optr\text{opt}_roptr 之间），更新 mid\text{mid}mid，然后继续递归分裂子问题。这样既可以动态（就是后面的值依赖于前面的 dp 值，普通的分治没法做）做，也可以避开二分队列那样难写的做法。
代码来自 OI-WIKI。
复杂度显然是 O(nlogn)O(n \log n)O(nlogn) 的，因为每一大层的复杂度总和总是 O(n)O(n)O(n)，O(logn)O(\log n)O(logn) 层，所以是 O(nlogn)O(n \log n)O(nlogn) 的。
注意这一行：
> for (int j = opt[l]; j <= opt[r]; ++j) check(j, mid);
check 的右端点 mid居然不动，左端点居然一直在非常好的 +1+1+1。这启示我们一些需要 O(n)O(n)O(n) 计算的 www 可以类似莫队一样移动指针。例如 w(l,r)w(l,r)w(l,r) 表示 [l..r][l..r][l..r] 中每个值的出现次数平方（注意这里是分别平方）的和。
这里比较特殊，可以直接先暴力算出 [optl..mid][\text{opt}_l..\text{mid}][optl ..mid]，然后一个一个往右边走，将左边算过的点删除（比如对于这个例子，可以维护值域数组 v[i] 表示值是 iii 数的个数，删除的时候先把原来的贡献减去 ans-=v[i]*v[i]，--v[a[i]]，再加上现在的贡献 ans+=v[i]*v[i]）。还有一种方法就是暴力算出 [min(optr,mid)..mid][\min(\text{opt}_r,\text{mid})..\text{mid}][min(optr ,mid)..mid]，然后再加入。
接下来我们解决形式 2（区间 dp 形式，用的较少）。
> 形式 2：在一个操场上摆放着一排 NNN 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的 222 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
> 试设计一个算法，计算出将 NNN 堆石子合并成一堆的最小得分。N≤2000N \le 2000N≤2000。P5569 弱化版。
显然最朴素的方程是 f(l,r)=minkf(l,k)+f(k+1,r)+w(l,r)f(l,r)=\min_k f(l,k)+f(k+1,r)+w(l,r)f(l,r)=mink f(l,k)+f(k+1,r)+w(l,r)。
这个时候 www 显然满足四边形不等式和区间包含单调性。所以这个时候有结论（1）：fff 满足四边形不等式。
这个时候 fff 满足四边形不等式，则有结论（2）：optl,r−1≤optl,r≤optl+1,r\text{opt}_{l,r-1} \le \text{opt}_{l,r} \le \text{opt}_{l+1,r}optl,r−1 ≤optl,r ≤optl+1,r 。
那么我们就可以直接枚举决策点区间去做。由于对于每个 lll，遍历的长度总和是 O(n)O(n)O(n) 的，所以复杂度是 O(n2)O(n^2)O(n2) 的。（这个很少用）
好了，决策单调性讲完了，这个时候我们就可以回收 wqs 所留的问题了。把式子拿过来：h(i)=max(h(i−1),−k+maxu(h(u)+w(u,i)))h(i)=\max(h(i-1),-k+\max_u(h(u)+w(u,i)))h(i)=max(h(i−1),−k+maxu (h(u)+w(u,i)))。www 可是满足四边形恒等式啊！具有决策单调性了啊！做完了（这里不影响 wqs 所需要记录的最优次数），时间复杂度 O(nlogn)O(n \log n)O(nlogn)，算上 wqs 二分就是 O(nlognlogV)O(n \log n \log
V)O(nlognlogV)，略逊于反悔贪心。
他和凸性的关系？咱们回到原来 wqs 二分的式子来。f(i,j)=max(f(i−1,j),maxk(f(k,j−1)+w(k,i)))f(i,j)=\max(f(i-1,j),\max_{k}(f(k,j-1)+w(k,i)))f(i,j)=max(f(i−1,j),maxk (f(k,j−1)+w(k,i)))。
这里直接给出结论：g(j)=maxf(i,j)g(j)=\max f(i,j)g(j)=maxf(i,j) 具有凸性。这个非常有用，返回原来的 wqs 问题，就可以直接证明它有凸性了。还有更多的证明凸性可以见 oi-wiki。
非常感谢：https://oi-wiki.org/dp/opt/quadrangle/
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
好的，让我们来看一道非常综合的题目！
题目。
题目大意
> 给定一个 nnn 个 A\texttt{A}A 和 nnn 个 B\texttt BB 组成的字符串 SSS，交换最少对元素使得：
>
> 存在一种方式，把 SSS 划分为 kkk 个子序列，每个子序列 A,B\texttt{A},\texttt BA,B 数量相等且所有 A\texttt AA 在所有 B\texttt BB 左边。
>
> 数据范围：n≤106n\le 10^6n≤106。（来自 DaiRuiChen007 的题解，https://www.luogu.com.cn/article/amcj6rjb ）
这里的题解都是基于 https://www.luogu.com.cn/article/amcj6rjb 理解的，讲的非常简短，但是有点笔误，代码中 inline array<ll,2> check(ll x) 使用 array 作为返回值，确实强！我这里主要是想讲的清楚一点。
遇见难题，先想想超级暴力咋做，一般是有前途的。
由于是子序列划分，所以普通的“f(i,j)f(i,j)f(i,j) 表示前 iii 个数划分为 jjj 段，这个状态的最小交换次数”完全不可做（他那个选的东西又不连续），所以考虑其他的。
换一个方面想，假设原序列就有解，先将 A 和 B 匹配，然后再把某些东西组合起来，这样也可以得到答案。
这启发我们将匹配的个数放到状态里。定义 f(i,j)f(i,j)f(i,j)，表示将前 iii 个 A 和 B 安排到了前 jjj 个乐曲，这样的最小交换次数。（后面我相信读者可以自己推出来）
这个时候也就有了一个非常好的性质：同一个乐曲中，选出来的 A 的次第是个区间。这个也很好证，如果不是个区间，反而不优（可以通过举例法或感性理解来猜到这个结论）。这里给个感性证明：你想咋选咋选，反正“区间”这一选法是一定存在在最优集合里面的。
这个就刚好解决了选点不连续的问题，那么 f(i,j)=mink=0i−1f(k,j−1)+w(k+1,i)f(i,j)=\min\limits^{i-1}_{k=0}f(k,j-1)+w(k+1,i)f(i,j)=k=0mini−1 f(k,j−1)+w(k+1,i)。w(l,r)w(l,r)w(l,r) 表示将第 [l..r][l..r][l..r] 个 A 和第 [l..r][l..r][l..r] 个 B 安排成一个合法的队伍需要的最少次数。
设 pip_ipi 表示第 iii 个 A 前面有多少个 B，那么 w(l,r)=∑i=lrmax(0,pi−l+1)w(l,r)=\sum\limits^{r}_{i=l}\max(0,p_i-l+1)w(l,r)=i=l∑r max(0,pi −l+1)。解释：这里是要将多少个 B 换到后面才有戏。
这个四边形不等式能证明（见后面），但是可以通过打表来证明。这个凸性也就证明出来了。由于 www 满足四边形不等式，所以 g(i)g(i)g(i) 具有凸性。
这里我们选择 wqs 二分。这样是 O(nlognlogV)O(n \log n \log V)O(nlognlogV) 的，但是此题 n≤106n \le 10^6n≤106。但是恭喜你获得了 878787 分！所以考虑更优的做法。
考虑将 www 优化。这个 www 拆开就是个 sss（前缀和）和 qqq（这里 qxq_xqx 指的是第一个 iii 使得 pi≥xp_i \ge xpi ≥x 的 iii）的表示了，你拆开就可以了。
这里由于 ppp 有决策单调性（？）所以你算 qiq_iqi 的时候可以直接找到 qi−1q_{i-1}qi−1 然后再往后遍历。这样是 O(n)O(n)O(n) 的。这样处理比较舒服。
把上面的 www 的式子拿过来，w(l,r)=∑i=lrmax(0,pi−l+1)w(l,r)=\sum\limits^{r}_{i=l}\max(0,p_i-l+1)w(l,r)=i=l∑r max(0,pi −l+1)。那么 w(l,r)=∑i=pl−1r(pi−l+1)=sr−spl−1−1−(r−pl−1+1)×(l−1)w(l,r)=\sum\limits^{r}_{i=p_{l-1}}(p_i-l+1)=s_r-s_{p_{l-1}-1}-(r-p_{l-1}+1)\times(l-1)w(l,r)=i=pl−1 ∑r (pi −l+1)=sr −spl−1 −1
−(r−pl−1 +1)×(l−1)（这里 si=∑j=1ipis_i=\sum\limits^{i}_{j=1}p_isi =j=1∑i pi ）。
这里来证明四边形不等式：首先 sss 抵消，然后你把位拆开，发现两项（两个乘法）中都是左边小于等于右边的（遇到这种题，大胆猜结论，如果你想在考场上证明，因为拆式子过于费劲，那耗费的时间足够重新写一份了）。
那么 g(i)=minjg(j)+w(j+1,i)=minjg(j−1)+w(j,i)=minj(g(j−1)+si−spj−1−(i−pj+1)×j)=minj((g(j−1)−spj−1+pj×j+j)+si+i×j)g(i)=\min_j g(j)+w(j+1,i)=\min_j g(j-1)+w(j,i)=\min_j (g(j-1)+s_i-s_{p_{j}-1}-(i-p_{j}+1)\times j)=\min_j ((g(j-1)-s_{p_{j}-1}+p_{j}\times j+j)+s_i+i\times j)g(i)=minj
g(j)+w(j+1,i)=minj g(j−1)+w(j,i)=minj (g(j−1)+si −spj −1 −(i−pj +1)×j)=minj ((g(j−1)−spj −1 +pj ×j+j)+si +i×j)（这里告诉一个非常好的公式换元方法：直接在小熊猫使用ctrl+f替换模式）（g 是 wqs 用）。
具体地（让我们来复习凸包！），当式子满足了这个标准形式：f(i)=maxjyj−kixjf(i)=\max _j y_j-k_ix_jf(i)=maxj yj −ki xj 就可以进行斜率优化（这里的 max 是 min 也可以）。这个时候 f(i)f(i)f(i) 就相当于这条斜线的 b 值。
回到原来，g(i)=si+minj((g(j−1)−spj−1+pj×j+j)+i×j)g(i)=s_i+\min_j ((g(j-1)-s_{p_{j}-1}+p_{j}\times j+j)+i\times j)g(i)=si +minj ((g(j−1)−spj −1 +pj ×j+j)+i×j)。这个时候令 yj=(g(j−1)−spj−1+pj×j+j)y_j=(g(j-1)-s_{p_{j}-1}+p_{j}\times j+j)yj =(g(j−1)−spj −1 +pj ×j+j)，xj=jx_j=jxj =j，ki=−ik_i=-iki
=−i，就可以做了。此时，显然，kkk 满足单调递减，xxx 满足单调递增，所以可以考虑一下直接拿单调栈来实现 O(n)O(n)O(n) 做 dp。
由于 xxx 越来越大，可以维护单调栈直接来维护凸包。又由于 kkk 单调递减，而凸包的性质满足它的 b 值是一个单谷函数，且谷底决策点一定从左向右移动。所以可以维护指针。这样我们就用 O(nlogV)O(n \log V)O(nlogV) 做完了（这里的 VVV 其实和 nnn 是同阶的）！
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
有笔误或者理解不够或者不懂得可以发在帖子下面。
