让 \(c\) 保存数组中所有最大的数，如果所有数都相等则 \(-1\)。
只需要记录每个序列的最小值和次小值，然后对次小值求前后缀和。
枚举最大值 \(mx\)，然后遍历 \(i:n\sim 1\)。对于 \(i\)，取最大数 \(x\) 满足 \(x\) 未选且 \(i\times x \le mx\)。
证明：假设 \(i\) 原本与 \(x\) 匹配，现在与 \(x1\) 匹配，显然 \(x1<x\)，否则 \(i\cdot x1>mx\)；\(x\) 与 \(i1\) 匹配，\(i1<i\) 因为更晚选。交换 \(x,x1\) 后总和增加 \((i-i1)(x-x1)>0\)，并且此时最大值依旧为 \(mx\)。
将每个 \(b_i,x_j,l_i\) 视作一个 “事件” 存到数组里，按坐标排个序，从最右边的位置向左遍历，在数轴上做类似扫描线的操作。（扫描点？）
定义 \(ans_i\) 为第 \(i\) 条线段最远能跳多远，\(p_j\) 为询问 \(x_j\) 的答案，显然 \(p_j=\max(x_j,ans_i|l_i\le x_j\le r_i)\)。
如果当前遇到了一个 \(b_i\)，更新 \(ans_i\) 为当前集合中所有 \(ans\) 的最大值（最靠右的），同时把 \(ans_i\) 加入集合中。
如果当前遇到了一个 \(x_j\)，更新 \(p_j\) 为当前集合中所有 \(ans\) 的最大值，再和 \(x_j\) 取 \(\min\)。
如果当前遇到了一个 \(l_i\)，从集合中删除 \(ans_i\)。
可以用 set 维护。
\(dp[i][j]\) 表示前 \(i\) 个数里选的区间长度和为 \(j\) 的最大价值。
\(dp[i][j]=\max(dp[i-1][j],dp[i-l][j-l]+cost(i-l+1,i)|1\le l\le j).\)
\(cost(i-l+1,i)\) 就是区间 \([i-l+1,i]\) 的价值。
观察发现 \(cost(l,r)=|b_l-a_r|+|b_r-a_l|\) 始终等于 \(\max(b_l-a_r+b_r-a_l,-b_l+a_r+b_r-a_l,b_l-a_r-b_r+a_l,-b_l+a_r-b_r+a_l).\)
同时，我们发现 \(dp\) 值之间只有 \(i-j\) 不变才能更新。
我们可以维护四个数组：\(mn1[x],mx1[x],mn2[x],mx2[x]\)，分别表示要求 \(i-j=x\) 时，\(-dp[i][j]+b_i+a_i\) 的最小值，\(dp[i][j]+b_i+a_i\) 的最大值，\(-dp[i][j]+b_i-a_i\) 的最小值，\(dp[i][j]+b_i-a_i\) 的最大值。
然后我们求 \(dp[i][j]\) 的时候，就可以根据 \(i-j\) 调用四个数组，根据上面 \(cost\) 的公式加减一下，四种情况都取 \(\max\)。大幅优化。
标签：le,max,最大值,CF1859,cost,ans,dp From： https://www.cnblogs.com/FLY-lai/p/18007895